Submission #1227591
Source Code Expand
/+ dub.sdl: name "A" dependency "dcomp" version=">=0.6.0" +/ import std.stdio, std.algorithm, std.range, std.conv; import std.typecons; import std.bigint; // import dcomp.foundation, dcomp.scanner; int main() { auto sc = new Scanner(stdin); long n, m; sc.read(n, m); long[][] a = new long[][](n, m); foreach (i; 0..n) { sc.read(a[i]); if (i && a[i-1][0] > a[i][0]) { writeln(-1); return 0; } } if (m == 1) { foreach (i; 1..n) { if (a[i-1][0] == a[i][0]) { writeln(-1); return 0; } } writeln(0); return 0; } // m >= 2 immutable INF = 10L^^9 + 10L^^7; long[][] C = new long[][](2020, 2020); C[0][0] = 1; foreach (i; 1..2020) { C[i][0] = C[i-1][0]; foreach (j; 1..2020) { C[i][j] = min(INF, C[i-1][j-1] + C[i-1][j]); } } long[] suc(long[] x, long c) { long[] y = x.dup; if (c == 0) return y; foreach (i; 0..m) { foreach (j; 0..i) { y[i] += x[j] * C[c-1+i-j][i-j]; } } return y; } long[] co = new long[n]; foreach (i; 1..n) { if (a[i-1][0] < a[i][0]) { continue; } // a[i-1][0] == a[i][0] long b2 = a[i-1][1] + a[i-1][0] * co[i-1]; if (b2 < a[i][1]) { continue; } long c = b2 - a[i][1]; if (c % a[i][0]) { co[i] = c / a[i][0] + 1; continue; } co[i] = c / a[i][0]; long mi = min(co[i-1], co[i]); long[] x1 = suc(a[i-1], co[i-1]-mi); long[] x2 = suc(a[i], co[i]-mi); if (cmp(x1, x2) != -1) { co[i]++; } } writeln(co.sum); return 0; } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */ // module dcomp.foundation; //fold(for old compiler) static if (__VERSION__ <= 2070) { template fold(fun...) if (fun.length >= 1) { auto fold(R, S...)(R r, S seed) { import std.algorithm : reduce; static if (S.length < 2) { return reduce!fun(seed, r); } else { import std.typecons : tuple; return reduce!fun(tuple(seed), r); } } } unittest { import std.stdio; auto l = [1, 2, 3, 4, 5]; assert(l.fold!"a+b"(10) == 25); } } version (X86) static if (__VERSION__ < 2071) { int bsf(ulong v) { foreach (i; 0..64) { if (v & (1UL << i)) return i; } return -1; } int bsr(ulong v) { foreach_reverse (i; 0..64) { if (v & (1UL << i)) return i; } return -1; } int popcnt(ulong v) { int c = 0; foreach (i; 0..64) { if (v & (1UL << i)) c++; } return c; } } /* 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; } char[512] lineBuf; char[] line; private bool succ() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (true) { while (!line.empty && line.front.isWhite) { line.popFront; } if (!line.empty) break; if (f.eof) return false; line = lineBuf[]; f.readln(line); } return true; } private bool readSingle(T)(ref T x) { import std.algorithm : findSplitBefore; import std.string : strip; import std.conv : parse; if (!succ()) return false; static if (isArray!T) { alias E = ElementType!T; static if (isSomeChar!E) { //string or char[10] etc //todo optimize auto r = line.findSplitBefore(" "); x = r[0].strip.dup; line = r[1]; } else { auto buf = line.split.map!(to!E).array; static if (isStaticArray!T) { //static assert(buf.length == T.length); } x = buf; line.length = 0; } } else { x = line.parse!T; } 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])); } unittest { import std.path : buildPath; import std.file : tempDir; import std.algorithm : equal; import std.stdio : File, writeln; import std.datetime; string fileName = buildPath(tempDir, "kyuridenanmaida.txt"); auto fout = File(fileName, "w"); foreach (i; 0..1_000_000) { fout.writeln(3*i, " ", 3*i+1, " ", 3*i+2); } fout.close; writeln("Scanner Speed Test(3*1,000,000 int)"); StopWatch sw; sw.start; Scanner sc = new Scanner(File(fileName, "r")); foreach (i; 0..500_000) { int a, b, c; sc.read(a, b, c); assert(a == 3*i); assert(b == 3*i+1); assert(c == 3*i+2); } foreach (i; 500_000..700_000) { int[3] d; sc.read(d); int a = d[0], b = d[1], c = d[2]; assert(a == 3*i); assert(b == 3*i+1); assert(c == 3*i+2); } foreach (i; 700_000..1_000_000) { int[] d; sc.read(d); assert(d.length == 3); int a = d[0], b = d[1], c = d[2]; assert(a == 3*i); assert(b == 3*i+1); assert(c == 3*i+2); } writeln(sw.peek.msecs, "ms"); }
Submission Info
Submission Time | |
---|---|
Task | B - Takahashi the Magician |
User | yosupo |
Language | D (LDC 0.17.0) |
Score | 1000 |
Code Size | 7007 Byte |
Status | RE |
Exec Time | 1463 ms |
Memory | 61436 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 800 / 800 | 0 / 200 | ||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt |
subtask1 | sample_1.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
All | sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
hack_1.txt | AC | 20 ms | 34428 KB |
hack_2.txt | AC | 20 ms | 34684 KB |
hack_3.txt | AC | 19 ms | 33532 KB |
hack_4.txt | AC | 1 ms | 256 KB |
hack_5.txt | AC | 19 ms | 34044 KB |
sample_1.txt | AC | 19 ms | 33020 KB |
sample_2.txt | AC | 1 ms | 256 KB |
sample_3.txt | AC | 19 ms | 34172 KB |
subtask_1_1.txt | AC | 20 ms | 33020 KB |
subtask_1_10.txt | AC | 19 ms | 33788 KB |
subtask_1_11.txt | AC | 191 ms | 61308 KB |
subtask_1_12.txt | AC | 20 ms | 32892 KB |
subtask_1_13.txt | AC | 20 ms | 33532 KB |
subtask_1_14.txt | AC | 19 ms | 33660 KB |
subtask_1_15.txt | AC | 202 ms | 60796 KB |
subtask_1_16.txt | AC | 204 ms | 45820 KB |
subtask_1_17.txt | AC | 204 ms | 46588 KB |
subtask_1_18.txt | AC | 202 ms | 60668 KB |
subtask_1_19.txt | AC | 19 ms | 32764 KB |
subtask_1_2.txt | AC | 19 ms | 33660 KB |
subtask_1_20.txt | AC | 2 ms | 380 KB |
subtask_1_3.txt | AC | 20 ms | 33660 KB |
subtask_1_4.txt | AC | 20 ms | 33404 KB |
subtask_1_5.txt | AC | 20 ms | 33788 KB |
subtask_1_6.txt | AC | 21 ms | 33788 KB |
subtask_1_7.txt | AC | 21 ms | 34044 KB |
subtask_1_8.txt | AC | 196 ms | 61052 KB |
subtask_1_9.txt | AC | 59 ms | 48636 KB |
subtask_2_1.txt | AC | 28 ms | 40700 KB |
subtask_2_10.txt | AC | 33 ms | 37500 KB |
subtask_2_11.txt | AC | 98 ms | 61052 KB |
subtask_2_12.txt | AC | 98 ms | 60796 KB |
subtask_2_13.txt | AC | 1463 ms | 52604 KB |
subtask_2_14.txt | AC | 98 ms | 61436 KB |
subtask_2_15.txt | AC | 20 ms | 33148 KB |
subtask_2_16.txt | AC | 4 ms | 9724 KB |
subtask_2_17.txt | AC | 4 ms | 9596 KB |
subtask_2_18.txt | AC | 1262 ms | 61052 KB |
subtask_2_19.txt | AC | 2 ms | 380 KB |
subtask_2_2.txt | AC | 241 ms | 49532 KB |
subtask_2_20.txt | AC | 20 ms | 34556 KB |
subtask_2_21.txt | AC | 20 ms | 33020 KB |
subtask_2_22.txt | AC | 20 ms | 33020 KB |
subtask_2_23.txt | AC | 20 ms | 33788 KB |
subtask_2_24.txt | AC | 20 ms | 34044 KB |
subtask_2_25.txt | AC | 19 ms | 33532 KB |
subtask_2_26.txt | AC | 20 ms | 34172 KB |
subtask_2_27.txt | AC | 20 ms | 34428 KB |
subtask_2_3.txt | AC | 109 ms | 48764 KB |
subtask_2_4.txt | AC | 216 ms | 44412 KB |
subtask_2_5.txt | AC | 99 ms | 61052 KB |
subtask_2_6.txt | AC | 99 ms | 60540 KB |
subtask_2_7.txt | AC | 100 ms | 40444 KB |
subtask_2_8.txt | AC | 24 ms | 35708 KB |
subtask_2_9.txt | AC | 38 ms | 39036 KB |
subtask_3_1.txt | AC | 20 ms | 34556 KB |
subtask_3_10.txt | AC | 204 ms | 45948 KB |
subtask_3_11.txt | AC | 204 ms | 46844 KB |
subtask_3_12.txt | AC | 5 ms | 9340 KB |
subtask_3_13.txt | AC | 20 ms | 33788 KB |
subtask_3_14.txt | AC | 2 ms | 380 KB |
subtask_3_2.txt | AC | 21 ms | 35068 KB |
subtask_3_3.txt | AC | 211 ms | 61308 KB |
subtask_3_4.txt | RE | 204 ms | 46844 KB |
subtask_3_5.txt | RE | 204 ms | 45948 KB |
subtask_3_6.txt | AC | 210 ms | 60540 KB |
subtask_3_7.txt | AC | 1204 ms | 52604 KB |
subtask_3_8.txt | AC | 1448 ms | 59388 KB |
subtask_3_9.txt | RE | 204 ms | 45948 KB |