Submission #1022539
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> #include <cassert> #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) #define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) typedef long long ll; using namespace std; template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); } template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); } int func(vector<ll> const & a, vector<ll> b) { int w = a.size(); if (a < b) { return 0; } else if (a[0] > b[0]) { return -1; } else { assert (a[0] == b[0]); if (w == 1) { return -1; } else { assert (b[0] >= 1); assert (a[1] >= b[1]); ll k = (a[1] - b[1] + b[0]-1) / b[0]; if (b[1] + k * b[0] > a[1]) { return k; } else { assert (b[1] + k * b[0] == a[1]); if (w == 2) { return k + 1; } else { repeat (j,k) { repeat (i,w-1) { b[i+1] += b[i]; if (b[i+1] > a[i+1]) break; } if (b[2] > a[2]) { b[1] = a[1]; break; } } return k + (a >= b); } } } } } int main() { int h, w; cin >> h >> w; vector<vector<ll> > f = vectors(h, w, ll()); repeat (y,h) repeat (x,w) cin >> f[y][x]; ll ans = 0; ll acc = 0; repeat (y,h-1) { vector<ll> const & a = f[y]; vector<ll> const & b = f[y+1]; if (a < b) { int k = func(b, a); if (k == -1) { acc = 0; } else { acc = max<int>(0, acc-k+1); } } else { int k = func(a, b); if (k == -1) { ans = -1; break; } else { acc += k; } } ans += acc; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Takahashi the Magician |
User | kimiyuki |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2403 Byte |
Status | WA |
Exec Time | 431 ms |
Memory | 8192 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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, 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 | 2 ms | 256 KB |
hack_2.txt | WA | 2 ms | 256 KB |
hack_3.txt | AC | 2 ms | 256 KB |
hack_4.txt | AC | 2 ms | 256 KB |
hack_5.txt | AC | 3 ms | 256 KB |
sample_1.txt | AC | 3 ms | 256 KB |
sample_2.txt | AC | 3 ms | 256 KB |
sample_3.txt | AC | 3 ms | 256 KB |
subtask_1_1.txt | AC | 3 ms | 256 KB |
subtask_1_10.txt | AC | 3 ms | 256 KB |
subtask_1_11.txt | AC | 361 ms | 8064 KB |
subtask_1_12.txt | AC | 3 ms | 256 KB |
subtask_1_13.txt | AC | 3 ms | 256 KB |
subtask_1_14.txt | AC | 2 ms | 256 KB |
subtask_1_15.txt | AC | 382 ms | 8064 KB |
subtask_1_16.txt | AC | 411 ms | 8064 KB |
subtask_1_17.txt | AC | 398 ms | 8064 KB |
subtask_1_18.txt | AC | 383 ms | 8064 KB |
subtask_1_19.txt | AC | 3 ms | 256 KB |
subtask_1_2.txt | AC | 3 ms | 256 KB |
subtask_1_20.txt | AC | 3 ms | 256 KB |
subtask_1_3.txt | AC | 3 ms | 256 KB |
subtask_1_4.txt | AC | 3 ms | 256 KB |
subtask_1_5.txt | AC | 4 ms | 256 KB |
subtask_1_6.txt | AC | 4 ms | 256 KB |
subtask_1_7.txt | AC | 4 ms | 384 KB |
subtask_1_8.txt | AC | 366 ms | 8064 KB |
subtask_1_9.txt | AC | 96 ms | 4224 KB |
subtask_2_1.txt | AC | 19 ms | 1024 KB |
subtask_2_10.txt | AC | 31 ms | 1664 KB |
subtask_2_11.txt | AC | 191 ms | 8064 KB |
subtask_2_12.txt | AC | 190 ms | 8192 KB |
subtask_2_13.txt | AC | 179 ms | 8064 KB |
subtask_2_14.txt | AC | 190 ms | 8064 KB |
subtask_2_15.txt | AC | 3 ms | 256 KB |
subtask_2_16.txt | AC | 189 ms | 8064 KB |
subtask_2_17.txt | AC | 187 ms | 8064 KB |
subtask_2_18.txt | AC | 202 ms | 8064 KB |
subtask_2_19.txt | AC | 3 ms | 256 KB |
subtask_2_2.txt | AC | 163 ms | 8064 KB |
subtask_2_20.txt | AC | 3 ms | 256 KB |
subtask_2_21.txt | AC | 3 ms | 256 KB |
subtask_2_22.txt | AC | 3 ms | 256 KB |
subtask_2_23.txt | AC | 3 ms | 256 KB |
subtask_2_24.txt | AC | 3 ms | 256 KB |
subtask_2_25.txt | AC | 2 ms | 256 KB |
subtask_2_26.txt | AC | 3 ms | 256 KB |
subtask_2_27.txt | AC | 3 ms | 256 KB |
subtask_2_3.txt | AC | 164 ms | 8064 KB |
subtask_2_4.txt | AC | 83 ms | 4224 KB |
subtask_2_5.txt | AC | 191 ms | 8064 KB |
subtask_2_6.txt | AC | 190 ms | 8064 KB |
subtask_2_7.txt | AC | 67 ms | 3328 KB |
subtask_2_8.txt | AC | 11 ms | 640 KB |
subtask_2_9.txt | AC | 40 ms | 2048 KB |
subtask_3_1.txt | AC | 3 ms | 256 KB |
subtask_3_10.txt | AC | 398 ms | 8064 KB |
subtask_3_11.txt | AC | 398 ms | 8064 KB |
subtask_3_12.txt | AC | 397 ms | 8064 KB |
subtask_3_13.txt | AC | 3 ms | 256 KB |
subtask_3_14.txt | AC | 3 ms | 256 KB |
subtask_3_2.txt | AC | 4 ms | 256 KB |
subtask_3_3.txt | AC | 401 ms | 8064 KB |
subtask_3_4.txt | AC | 431 ms | 8064 KB |
subtask_3_5.txt | AC | 399 ms | 8064 KB |
subtask_3_6.txt | AC | 401 ms | 8064 KB |
subtask_3_7.txt | AC | 316 ms | 8064 KB |
subtask_3_8.txt | AC | 379 ms | 8064 KB |
subtask_3_9.txt | AC | 398 ms | 8064 KB |