Submission #1061653
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;
int U;
long[2][] d;
long[][][] dp;
bool[][][] used;
long calcBase(int p, int a, int c) {
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 ans;
}
memoCont!calcBase calc;
int main() {
calc.init([[0, 5005], [0,5005], [0, 1]]);
// 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 /Users/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]));
}
/* IMPORT /Users/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));
static immutable N = Args.length;
int[2][N] rng;
int[N] len;
R[] dp;
bool[] used;
void init(int[2][N] rng) {
this.rng = rng;
len = rng[].map!(a => a[1]-a[0]+1).array;
int sz = len.reduce!"a*b";
dp = new R[sz];
used = new bool[sz];
}
R opCall(Args args) {
int idx, base = 1;
foreach (i, v; args) {
assert(rng[i][0] <= v && v <= rng[i][1]);
idx += base*(v - rng[i][0]);
base *= len[i];
}
if (used[idx]) return dp[idx];
used[idx] = true;
auto r = pred(args);
dp[idx] = r;
return r;
}
}
unittest {
// import dcomp.numeric.primitive;
// import dcomp.numeric.modint;
alias Mint = ModInt!(10^^9+7);
auto fact = factTable!Mint(100);
auto iFac = invFactTable!Mint(100);
Mint C0(int a, int b) {
if (a < 0 || a < b) return Mint(0);
return fact[a]*iFac[b]*iFac[a-b];
}
struct A {
static memoCont!C1base C1;
static Mint C1base(int a, int b) {
if (a == 0) {
if (b == 0) return Mint(1);
return Mint(0);
}
if (b < 0) return Mint(0);
return C1(a-1, b-1) + C1(a-1, b);
}
}
A.C1.init([[0, 100], [-2, 100]]);
foreach (i; 0..100) {
foreach (j; 0..100) {
assert(C0(i, j) == A.C1(i, j));
}
}
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/numeric/modint.d */
// module dcomp.numeric.modint;
// import dcomp.numeric.primitive;
struct ModInt(uint MD) if (MD < int.max) {
import std.conv : to;
uint v;
this(int v) {this.v = (long(v)%MD+MD)%MD;}
this(long v) {this.v = (v%MD+MD)%MD;}
auto normS(uint x) {return (x<MD)?x:x-MD;}
auto make(uint x) {ModInt m; m.v = x; return m;}
auto opBinary(string op:"+")(ModInt r) {return make(normS(v+r.v));}
auto opBinary(string op:"-")(ModInt r) {return make(normS(v+MD-r.v));}
auto opBinary(string op:"*")(ModInt r) {return make( (long(v)*r.v%MD).to!uint );}
auto opBinary(string op:"/")(ModInt r) {return this*inv(r);}
auto opOpAssign(string op)(ModInt r) {return mixin ("this=this"~op~"r");}
static ModInt inv(ModInt x) {return ModInt(extGcd!int(x.v, MD)[0]);}
string toString() {return v.to!string;}
}
unittest {
static assert( is(ModInt!(uint(1000000000) * 2))); //not overflow
static assert(!is(ModInt!(uint(1145141919) * 2))); //overflow!
alias Mint = ModInt!(10^^9+7);
// negative check
assert(Mint(-1).v == 10^^9 + 6);
assert(Mint(-1L).v == 10^^9 + 6);
Mint a = 48;
Mint b = Mint.inv(a);
assert(b.v == 520833337);
Mint c = Mint(15);
Mint d = Mint(3);
assert((c/d).v == 5);
}
struct DModInt {
import std.conv : to;
uint MD, v;
this(int v, uint md) {
MD = md;
this.v = ((long(v)%MD+MD)%MD).to!uint;
}
this(long v, uint md) {
MD = md;
this.v = ((v%MD+MD)%MD).to!uint;
}
auto normS(uint x) {return (x<MD)?x:x-MD;}
auto make(uint x) {DModInt m; m.MD = MD; m.v = x; return m;}
auto opBinary(string op:"+")(DModInt r) {
assert(MD == r.MD);
return make(normS(v+r.v));
}
auto opBinary(string op:"-")(DModInt r) {
assert(MD == r.MD);
return make(normS(v+MD-r.v));
}
auto opBinary(string op:"*")(DModInt r) {
assert(MD == r.MD);
return make((long(v)*r.v%MD).to!uint);
}
auto opBinary(string op:"/")(DModInt r) {
assert(MD == r.MD);
return this*inv(r);
}
auto opOpAssign(string op)(DModInt r) {return mixin ("this=this"~op~"r");}
static DModInt inv(DModInt x) {
return DModInt(extGcd!int(x.v, x.MD)[0], x.MD);
}
string toString() {return v.to!string;}
}
unittest {
immutable MD = 10^^9 + 7;
alias Mint = DModInt;
//negative check
assert(Mint(-1, MD).v == 10^^9 + 6);
assert(Mint(-1L, MD).v == 10^^9 + 6);
Mint a = Mint(48, MD);
Mint b = Mint.inv(a);
assert(b.v == 520833337);
Mint c = Mint(15, MD);
Mint d = Mint(3, MD);
assert((c/d).v == 5);
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/numeric/primitive.d */
// module dcomp.numeric.primitive;
import std.traits;
T pow(T, U)(T x, U n) { return pow(x, n, T(1)); }
T pow(T, U)(T x, U n, T e) {
while (n) {
if (n & 1) e *= x;
x *= x;
n /= 2;
}
return e;
}
unittest {
assert(pow(3, 5) == 243);
assert(pow(3, 5, 2) == 486);
}
T lcm(T)(in T a, in T b) {
import std.numeric : gcd;
return a / gcd(a,b) * b;
}
unittest {
assert(lcm(2, 4) == 4);
assert(lcm(3, 5) == 15);
assert(lcm(1, 1) == 1);
assert(lcm(0, 100) == 0);
}
//a*T[0]+b*T[1]=T[2], T[2]=gcd
//todo: to binary extgcd
T[3] extGcd(T)(in T a, in T b)
if (!isIntegral!T || isSigned!T) //unsignedはNG
{
if (b==0) {
return [1, 0, a];
} else {
auto e = extGcd(b, a%b);
return [e[1], e[0]-a/b*e[1], e[2]];
}
}
unittest {
import std.numeric : gcd;
foreach (i; 0..100) {
foreach (j; 0..100) {
auto e = extGcd(i, j);
assert(e[2] == gcd(i, j));
assert(e[0] * i + e[1] * j == e[2]);
}
}
}
T[] factTable(T)(size_t length) {
import std.range : take, recurrence;
import std.array : array;
return T(1).recurrence!((a, n) => a[n-1]*T(n)).take(length).array;
}
// optimize
T[] invFactTable(T)(size_t length) {
import std.range : take, recurrence;
import std.array : array;
return T(1).recurrence!((a, n) => a[n-1]/T(n)).take(length).array;
}
unittest {
import std.stdio;
// import dcomp.numeric.modint;
alias Mint = ModInt!(10^^9 + 7);
auto r = factTable!Mint(20);
Mint a = 1;
assert(r[0] == Mint(1));
foreach (i; 1..20) {
a *= Mint(i);
assert(r[i] == a);
}
auto p = invFactTable!Mint(20);
foreach (i; 1..20) {
assert((r[i]*p[i]).v == 1);
}
}
Submission Info
Submission Time |
|
Task |
F - Intervals |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
0 |
Code Size |
10112 Byte |
Status |
MLE |
Exec Time |
716 ms |
Memory |
442876 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
MLE |
627 ms |
442748 KB |
001.txt |
MLE |
521 ms |
441980 KB |
002.txt |
MLE |
621 ms |
442748 KB |
003.txt |
MLE |
716 ms |
442492 KB |
004.txt |
MLE |
624 ms |
442748 KB |
005.txt |
MLE |
606 ms |
442236 KB |
006.txt |
MLE |
620 ms |
442748 KB |
007.txt |
MLE |
557 ms |
442364 KB |
008.txt |
MLE |
623 ms |
442748 KB |
009.txt |
MLE |
513 ms |
441852 KB |
010.txt |
MLE |
623 ms |
442748 KB |
011.txt |
MLE |
549 ms |
442236 KB |
012.txt |
MLE |
620 ms |
442748 KB |
013.txt |
MLE |
508 ms |
441724 KB |
014.txt |
MLE |
622 ms |
442748 KB |
015.txt |
MLE |
553 ms |
441980 KB |
016.txt |
MLE |
624 ms |
442748 KB |
017.txt |
MLE |
589 ms |
442492 KB |
018.txt |
MLE |
620 ms |
442748 KB |
019.txt |
MLE |
629 ms |
442364 KB |
020.txt |
MLE |
495 ms |
441468 KB |
021.txt |
MLE |
499 ms |
441468 KB |
022.txt |
MLE |
623 ms |
442748 KB |
023.txt |
MLE |
621 ms |
442748 KB |
024.txt |
MLE |
620 ms |
442748 KB |
025.txt |
MLE |
621 ms |
442748 KB |
026.txt |
MLE |
620 ms |
442748 KB |
027.txt |
MLE |
622 ms |
442748 KB |
028.txt |
MLE |
625 ms |
442748 KB |
029.txt |
MLE |
622 ms |
442748 KB |
030.txt |
MLE |
622 ms |
442876 KB |
031.txt |
MLE |
625 ms |
442748 KB |
032.txt |
MLE |
624 ms |
442748 KB |
033.txt |
MLE |
625 ms |
442748 KB |
034.txt |
MLE |
625 ms |
442748 KB |
035.txt |
MLE |
622 ms |
442748 KB |
036.txt |
MLE |
622 ms |
442748 KB |
037.txt |
MLE |
623 ms |
442748 KB |
038.txt |
MLE |
620 ms |
442748 KB |
039.txt |
MLE |
623 ms |
442748 KB |
040.txt |
MLE |
621 ms |
442748 KB |
041.txt |
MLE |
621 ms |
442748 KB |
042.txt |
MLE |
623 ms |
442748 KB |
example0.txt |
MLE |
500 ms |
441468 KB |
example1.txt |
MLE |
499 ms |
441468 KB |