Submission #1227611
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 (ph; 0..c) { bool la = false; foreach (i; 1..m) { y[i] += y[i-1]; if (y[i] >= INF) la = true; } if (la) break; } 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 | 200 |
Code Size | 7095 Byte |
Status | WA |
Exec Time | 199 ms |
Memory | 61564 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 0 / 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 | 32892 KB |
hack_2.txt | AC | 20 ms | 33660 KB |
hack_3.txt | AC | 19 ms | 33532 KB |
hack_4.txt | AC | 1 ms | 256 KB |
hack_5.txt | AC | 20 ms | 34300 KB |
sample_1.txt | AC | 20 ms | 33916 KB |
sample_2.txt | AC | 1 ms | 256 KB |
sample_3.txt | AC | 20 ms | 33020 KB |
subtask_1_1.txt | AC | 20 ms | 33916 KB |
subtask_1_10.txt | AC | 20 ms | 34684 KB |
subtask_1_11.txt | AC | 178 ms | 60668 KB |
subtask_1_12.txt | AC | 20 ms | 34044 KB |
subtask_1_13.txt | AC | 21 ms | 34812 KB |
subtask_1_14.txt | AC | 20 ms | 33020 KB |
subtask_1_15.txt | AC | 186 ms | 59644 KB |
subtask_1_16.txt | AC | 191 ms | 45308 KB |
subtask_1_17.txt | AC | 191 ms | 46844 KB |
subtask_1_18.txt | AC | 189 ms | 60540 KB |
subtask_1_19.txt | AC | 20 ms | 34300 KB |
subtask_1_2.txt | AC | 20 ms | 32892 KB |
subtask_1_20.txt | AC | 2 ms | 380 KB |
subtask_1_3.txt | AC | 20 ms | 34684 KB |
subtask_1_4.txt | AC | 20 ms | 33148 KB |
subtask_1_5.txt | AC | 20 ms | 33532 KB |
subtask_1_6.txt | AC | 21 ms | 34940 KB |
subtask_1_7.txt | AC | 21 ms | 34172 KB |
subtask_1_8.txt | AC | 180 ms | 60668 KB |
subtask_1_9.txt | AC | 58 ms | 47356 KB |
subtask_2_1.txt | AC | 29 ms | 41340 KB |
subtask_2_10.txt | AC | 31 ms | 38652 KB |
subtask_2_11.txt | AC | 98 ms | 61564 KB |
subtask_2_12.txt | AC | 98 ms | 60540 KB |
subtask_2_13.txt | AC | 89 ms | 52604 KB |
subtask_2_14.txt | AC | 99 ms | 61052 KB |
subtask_2_15.txt | AC | 20 ms | 33148 KB |
subtask_2_16.txt | AC | 4 ms | 9212 KB |
subtask_2_17.txt | AC | 4 ms | 9852 KB |
subtask_2_18.txt | WA | 104 ms | 61564 KB |
subtask_2_19.txt | AC | 2 ms | 380 KB |
subtask_2_2.txt | AC | 82 ms | 49788 KB |
subtask_2_20.txt | AC | 20 ms | 34428 KB |
subtask_2_21.txt | AC | 20 ms | 34428 KB |
subtask_2_22.txt | AC | 20 ms | 34556 KB |
subtask_2_23.txt | AC | 20 ms | 33916 KB |
subtask_2_24.txt | AC | 20 ms | 33788 KB |
subtask_2_25.txt | AC | 19 ms | 33532 KB |
subtask_2_26.txt | AC | 20 ms | 33532 KB |
subtask_2_27.txt | AC | 20 ms | 34812 KB |
subtask_2_3.txt | AC | 81 ms | 49020 KB |
subtask_2_4.txt | AC | 51 ms | 43388 KB |
subtask_2_5.txt | AC | 98 ms | 59900 KB |
subtask_2_6.txt | WA | 97 ms | 61180 KB |
subtask_2_7.txt | AC | 45 ms | 40700 KB |
subtask_2_8.txt | AC | 23 ms | 36220 KB |
subtask_2_9.txt | AC | 35 ms | 39804 KB |
subtask_3_1.txt | WA | 20 ms | 34940 KB |
subtask_3_10.txt | AC | 191 ms | 46972 KB |
subtask_3_11.txt | AC | 191 ms | 45692 KB |
subtask_3_12.txt | AC | 5 ms | 9340 KB |
subtask_3_13.txt | AC | 20 ms | 32892 KB |
subtask_3_14.txt | AC | 2 ms | 380 KB |
subtask_3_2.txt | WA | 21 ms | 34812 KB |
subtask_3_3.txt | AC | 196 ms | 61436 KB |
subtask_3_4.txt | WA | 197 ms | 59644 KB |
subtask_3_5.txt | WA | 199 ms | 61180 KB |
subtask_3_6.txt | AC | 198 ms | 60028 KB |
subtask_3_7.txt | WA | 150 ms | 52604 KB |
subtask_3_8.txt | WA | 188 ms | 60540 KB |
subtask_3_9.txt | WA | 198 ms | 60924 KB |