Submission #1022540
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) { if (b[i] > a[i]) break; b[i+1] += b[i]; assert (b[i+1] >= 1); } 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 | 2450 Byte |
Status | WA |
Exec Time | 408 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 | 3 ms | 256 KB |
hack_2.txt | WA | 3 ms | 256 KB |
hack_3.txt | AC | 3 ms | 256 KB |
hack_4.txt | AC | 3 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 | 364 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 | 3 ms | 256 KB |
subtask_1_15.txt | AC | 382 ms | 8064 KB |
subtask_1_16.txt | AC | 401 ms | 8064 KB |
subtask_1_17.txt | AC | 408 ms | 8064 KB |
subtask_1_18.txt | AC | 386 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 | 369 ms | 8064 KB |
subtask_1_9.txt | AC | 100 ms | 4224 KB |
subtask_2_1.txt | AC | 19 ms | 1024 KB |
subtask_2_10.txt | AC | 32 ms | 1664 KB |
subtask_2_11.txt | AC | 193 ms | 8064 KB |
subtask_2_12.txt | AC | 193 ms | 8064 KB |
subtask_2_13.txt | AC | 177 ms | 8064 KB |
subtask_2_14.txt | AC | 192 ms | 8064 KB |
subtask_2_15.txt | AC | 3 ms | 256 KB |
subtask_2_16.txt | AC | 197 ms | 8064 KB |
subtask_2_17.txt | AC | 189 ms | 8192 KB |
subtask_2_18.txt | AC | 189 ms | 8064 KB |
subtask_2_19.txt | AC | 3 ms | 256 KB |
subtask_2_2.txt | AC | 165 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 | 3 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 | 165 ms | 8064 KB |
subtask_2_4.txt | AC | 83 ms | 4224 KB |
subtask_2_5.txt | AC | 192 ms | 8064 KB |
subtask_2_6.txt | AC | 192 ms | 8064 KB |
subtask_2_7.txt | AC | 68 ms | 3328 KB |
subtask_2_8.txt | AC | 12 ms | 640 KB |
subtask_2_9.txt | AC | 40 ms | 2048 KB |
subtask_3_1.txt | AC | 4 ms | 256 KB |
subtask_3_10.txt | AC | 401 ms | 8064 KB |
subtask_3_11.txt | AC | 400 ms | 8064 KB |
subtask_3_12.txt | AC | 400 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 | 403 ms | 8192 KB |
subtask_3_4.txt | AC | 404 ms | 8064 KB |
subtask_3_5.txt | AC | 403 ms | 8064 KB |
subtask_3_6.txt | AC | 403 ms | 8064 KB |
subtask_3_7.txt | AC | 304 ms | 8064 KB |
subtask_3_8.txt | AC | 382 ms | 8064 KB |
subtask_3_9.txt | AC | 400 ms | 8064 KB |