Submission #1060021
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.4.0"
+/
import std.stdio, std.algorithm, std.conv, std.range;
import std.typecons, std.math;
// import dcomp.scanner, dcomp.functional;
alias E = Tuple!(int, "to");
int U;
long[2][] d;
long[][][] dp;
bool[][][] used;
long calc(int p, int a, int c) {
if (used[c][p][a]) return dp[c][p][a];
used[c][p][a] = true;
if (p == d.length) return 0;
long[2] nw = d[p];
int b = p-a;
long ans = 10L^^18;
if (c == 0) {
ans = min(ans, U*(nw[0]+nw[1]) + calc(p+1, a, 1));
}
if (a < U) {
ans = min(ans, a*(nw[0]+nw[1]) + nw[1] + calc(p+1, a+1, c));
}
if (b < U) {
ans = min(ans, b*(nw[0]+nw[1]) + nw[0] + calc(p+1, a, c));
}
return dp[c][p][a] = ans;
}
int main() {
dp = new long[][][](2, 5005, 2505);
used = new bool[][][](2, 5005, 2505);
auto sc = new Scanner(stdin);
int n;
sc.read(n);
d = new long[2][n];
foreach (i; 0..n) {
sc.read(d[i]);
}
d.sort!"a[0]+a[1] > b[0]+b[1]";
U = n/2;
writeln(calc(0, 0, 1-n%2));
return 0;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/functional.d */
// module dcomp.functional;
struct memoCont(alias pred) {
import std.range, std.algorithm, std.conv;
import std.string : join;
import std.traits : ReturnType, ParameterTypeTuple, isIntegral;
import std.typecons : tuple, Tuple;
import std.meta;
alias R = ReturnType!pred;
alias Args = ParameterTypeTuple!pred;
static assert (allSatisfy!(isIntegral, Args)); // should be int only?
static immutable N = Args.length;
static string toTuple(string s) { //int[N] -> (N[0], N[1], N[2], ...)
return "(" ~ iota(N).map!(i => s~"["~i.to!string~"]").join(",") ~ ")";
}
static string toArray(string s) { //int[N] -> [N[0]][N[1]][N[2]]...
return iota(N).map!(i => "["~s~"["~i.to!string~"]]").join("");
}
template NArray(T, int N) {
static if (!N) alias NArray = T;
else alias NArray = NArray!(T, N-1)[];
}
int[2][N] rng;
NArray!(R, N) dp;
NArray!(bool, N) used;
void init(int[2][N] rng) {
this.rng = rng;
int[N] len = rng[].map!(a => a[1]-a[0]+1).array;
//dp = new typeof(dp)(len[0], len[1], ..., len[N-1])
//used = new typeof(used)(len[0], len[1], ..., len[N-1])
dp = mixin("new typeof(dp)"~toTuple("len"));
used = mixin("new typeof(used)"~toTuple("len"));
}
R opCall(Args args) {
int[N] idx;
foreach (i, v; args) {
assert(rng[i][0] <= v && v <= rng[i][1]);
idx[i] = v - rng[i][0];
}
//if (used[idx[0]]..[idx[N-1]]) dp[idx[0]]..[idx[N-1]]
//used[idx[0]]..[idx[N-1]] = true
if (mixin("used"~toArray("idx"))) return mixin("dp"~toArray("idx"));
mixin("used"~toArray("idx")) = true;
auto r = pred(args);
//dp[idx[0]]..[idx[N-1]] = r
mixin("dp"~toArray("idx")) = r;
return r;
}
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;
class Scanner {
import std.stdio : File;
import std.conv : to;
import std.range : front, popFront, array, ElementType;
import std.array : split;
import std.traits : isSomeChar, isStaticArray, isArray;
import std.algorithm : map;
File f;
this(File f) {
this.f = f;
}
string[] buf;
private bool succ() {
while (!buf.length) {
if (f.eof) return false;
buf = f.readln.split;
}
return true;
}
private bool readSingle(T)(ref T x) {
if (!succ()) return false;
static if (isArray!T) {
alias E = ElementType!T;
static if (isSomeChar!E) {
//string or char[10] etc
x = buf.front;
buf.popFront;
} else {
static if (isStaticArray!T) {
//static
assert(buf.length == T.length);
}
x = buf.map!(to!E).array;
buf.length = 0;
}
} else {
x = buf.front.to!T;
buf.popFront;
}
return true;
}
int read(T, Args...)(ref T x, auto ref Args args) {
if (!readSingle(x)) return 0;
static if (args.length == 0) {
return 1;
} else {
return 1 + read(args);
}
}
}
unittest {
import std.path : buildPath;
import std.file : tempDir;
import std.algorithm : equal;
import std.stdio : File;
string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
auto fout = File(fileName, "w");
fout.writeln("1 2 3");
fout.writeln("ab cde");
fout.writeln("1.0 1.0 2.0");
fout.close;
Scanner sc = new Scanner(File(fileName, "r"));
int a;
int[2] b;
char[2] c;
string d;
double e;
double[] f;
sc.read(a, b, c, d, e, f);
assert(a == 1);
assert(equal(b[], [2, 3]));
assert(equal(c[], "ab"));
assert(equal(d, "cde"));
assert(e == 1.0);
assert(equal(f, [1.0, 2.0]));
}
Submission Info
Submission Time |
|
Task |
F - Intervals |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
1000 |
Code Size |
5385 Byte |
Status |
AC |
Exec Time |
910 ms |
Memory |
242556 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1000 / 1000 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0.txt, example1.txt |
All |
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, example0.txt, example1.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
AC |
568 ms |
242556 KB |
001.txt |
AC |
342 ms |
241788 KB |
002.txt |
AC |
566 ms |
242556 KB |
003.txt |
AC |
910 ms |
242300 KB |
004.txt |
AC |
568 ms |
242556 KB |
005.txt |
AC |
569 ms |
242044 KB |
006.txt |
AC |
567 ms |
242556 KB |
007.txt |
AC |
422 ms |
242172 KB |
008.txt |
AC |
568 ms |
242556 KB |
009.txt |
AC |
320 ms |
241532 KB |
010.txt |
AC |
567 ms |
242556 KB |
011.txt |
AC |
402 ms |
242044 KB |
012.txt |
AC |
566 ms |
242556 KB |
013.txt |
AC |
316 ms |
241532 KB |
014.txt |
AC |
567 ms |
242556 KB |
015.txt |
AC |
411 ms |
241788 KB |
016.txt |
AC |
567 ms |
242556 KB |
017.txt |
AC |
494 ms |
242300 KB |
018.txt |
AC |
564 ms |
242556 KB |
019.txt |
AC |
641 ms |
242044 KB |
020.txt |
AC |
298 ms |
241148 KB |
021.txt |
AC |
298 ms |
241148 KB |
022.txt |
AC |
568 ms |
242556 KB |
023.txt |
AC |
562 ms |
242556 KB |
024.txt |
AC |
565 ms |
242556 KB |
025.txt |
AC |
569 ms |
242556 KB |
026.txt |
AC |
568 ms |
242556 KB |
027.txt |
AC |
567 ms |
242556 KB |
028.txt |
AC |
564 ms |
242556 KB |
029.txt |
AC |
565 ms |
242556 KB |
030.txt |
AC |
565 ms |
242556 KB |
031.txt |
AC |
567 ms |
242556 KB |
032.txt |
AC |
565 ms |
242556 KB |
033.txt |
AC |
568 ms |
242556 KB |
034.txt |
AC |
566 ms |
242556 KB |
035.txt |
AC |
564 ms |
242556 KB |
036.txt |
AC |
586 ms |
242556 KB |
037.txt |
AC |
566 ms |
242556 KB |
038.txt |
AC |
567 ms |
242556 KB |
039.txt |
AC |
564 ms |
242556 KB |
040.txt |
AC |
567 ms |
242556 KB |
041.txt |
AC |
569 ms |
242556 KB |
042.txt |
AC |
570 ms |
242556 KB |
example0.txt |
AC |
298 ms |
241148 KB |
example1.txt |
AC |
300 ms |
241148 KB |