QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#131193 | #4207. Uplifting Excursion | bashkort# | 90 | 3240ms | 54324kb | C++20 | 4.8kb | 2023-07-26 17:38:25 | 2024-07-04 00:56:16 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int X = 1e6 + 228, M = 300 + 2;
constexpr ll infLL = 1e18;
ll dp_[2 * X + 1], a_[2 * M + 1], b_[2 * M + 1], dq_[2 * X + 1];
auto dp = dp_ + X, dq = dq_ + X, a = a_ + M, b = b_ + M;
struct MaxQueue {
deque<ll> qwq;
void ins(ll x) {
if (x < -infLL) {
return;
}
while (!qwq.empty() && qwq.back() < x) {
qwq.pop_back();
}
qwq.push_back(x);
}
void del(ll x) {
if (x < -infLL) {
return;
}
if (!qwq.empty() && qwq.front() == x) {
qwq.pop_front();
}
}
ll top() {
return qwq.empty() ? ll(-3e18) : qwq.front();
}
void clear() {
qwq.clear();
}
};
MaxQueue q[M];
int mod(int x, int y) {
if (y < 0) {
x *= -1, y *= -1;
}
if ((x %= y) < 0) {
x += y;
}
return x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m;
ll L;
cin >> m >> L;
fill(begin(dp_), end(dp_), -3e18);
for (int i = -m; i <= m; ++i) {
cin >> a[i];
}
if (L < 0 && accumulate(a - m, a + 1, 0LL) == 0) {
cout << "impossible\n";
return 0;
}
if (L < 0) {
L = -L;
reverse(a - m, a + m + 1);
}
ll s = 0, cnt = 0;
for (int i = -m; i <= 0; ++i) {
b[i] = a[i];
s += a[i] * i;
}
for (int i = 1; i <= m; ++i) {
b[i] = min(a[i], (max(0LL, L - s) + i - 1) / i);
s += b[i] * i;
}
for (int i = -m; i < 0 && s < L; ++i) {
ll c = s - a[i] * i;
if (c >= L) {
ll now = (L - s - i - 1) / -i;
assert(s - i * now >= L && s - i * (now - 1) < L);
b[i] -= now;
s -= i * now;
} else {
s -= a[i] * i;
b[i] = 0;
}
}
cnt = accumulate(b - m, b + m + 1, 0LL);
if (s < L) {
cout << "impossible\n";
return 0;
}
dp[0] = 0;
auto canAdd = [&](int l, ll cnt) {
if (cnt == 0) {
return;
}
copy(dp - X, dp + X + 1, dq - X);
for (int i = 0; i < abs(l); ++i) {
q[i].clear();
}
cnt *= abs(l);
if (l > 0) {
for (int x = -X + 1, rem = mod(x, l), div = x / l; x < X; ++x, rem = rem == l - 1 ? 0 : rem + 1, div = rem == 0 ? div + 1 : div) {
dp[x] = max(dq[x], q[rem].top() + div);
if (dq[x] > -infLL) {
q[rem].ins(dq[x] -= div);
}
if (x - cnt > -X) {
q[rem].del(dq[x - cnt]);
}
}
} else if (l < 0) {
l = -l;
for (int x = X - 1, rem = mod(x, l), div = x / l; x > -X; --x, div = rem == 0 ? div - 1 : div, rem = rem == 0 ? l - 1 : rem - 1) {
dp[x] = max(dq[x], q[rem].top() - div);
if (dq[x] > -infLL) {
q[rem].ins(dq[x] += div);
}
if (x + cnt * l < X) {
q[rem].del(dq[x + cnt]);
}
}
}
};
auto canDelete = [&](int l, ll cnt) {
if (cnt == 0) {
return;
}
copy(dp - X, dp + X + 1, dq - X);
for (int i = 0; i < abs(l); ++i) {
q[i].clear();
}
cnt *= abs(l);
if (l > 0) {
for (int x = X - 1, rem = mod(x, l), div = x / l; x > -X; --x, div = rem == 0 ? div - 1 : div, rem = rem == 0 ? l - 1 : rem - 1) {
dp[x] = max(dq[x], q[rem].top() + div);
if (dq[x] > -infLL) {
q[rem].ins(dq[x] -= div);
}
if (x + cnt < X) {
q[rem].del(dq[x + cnt]);
}
}
} else if (l < 0) {
l = -l;
for (int x = -X + 1, rem = mod(x, l), div = x / l; x < X; ++x, rem = rem == l - 1 ? 0 : rem + 1, div = rem == 0 ? div + 1 : div) {
dp[x] = max(dq[x], q[rem].top() - div);
if (dq[x] > -infLL) {
q[rem].ins(dq[x] += div);
}
if (x - cnt * l > -X) {
q[rem].del(dq[x - cnt]);
}
}
}
};
for (int i = -m; i <= m; ++i) {
if (i != 0) {
canAdd(i, a[i] - b[i]);
canDelete(i, b[i]);
}
}
ll need = L - s;
if (need <= -X || need >= X || cnt + dp[need] < 0) {
cout << "impossible\n";
return 0;
}
cout << cnt + dp[need] << '\n';
return 0;
}
详细
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 16ms
memory: 35012kb
input:
1 5 0 0 6
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 38ms
memory: 35000kb
input:
50 2303 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 5 25 50 0
output:
47
result:
ok single line: '47'
Test #3:
score: 0
Accepted
time: 656ms
memory: 35044kb
input:
50 -17964 18 21 8 47 11 30 0 34 11 22 10 29 14 39 25 42 16 47 6 39 0 4 28 5 4 39 43 47 14 49 24 37 22 47 23 31 18 28 43 14 44 26 46 40 27 17 41 7 13 25 27 20 17 13 23 30 9 16 5 25 46 22 35 44 34 39 19 19 33 11 30 30 41 20 1 9 39 34 31 26 28 13 13 21 45 11 32 30 35 37 22 31 1 9 43 18 31 41 34 39 2
output:
2060
result:
ok single line: '2060'
Test #4:
score: 0
Accepted
time: 23ms
memory: 35012kb
input:
3 5 3 1 0 2 0 0 2
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 58ms
memory: 35056kb
input:
10 7 0 0 0 0 0 0 0 0 0 0 7 10 5 8 10 0 9 0 4 6 2
output:
14
result:
ok single line: '14'
Test #6:
score: 0
Accepted
time: 0ms
memory: 19860kb
input:
50 -779348731063743410 36 40 12 5 42 47 17 35 47 44 16 45 5 41 26 7 28 23 15 27 17 19 44 18 12 30 27 13 24 5 34 11 36 39 38 32 0 34 24 11 18 26 43 50 1 29 18 28 41 38 41 19 22 0 9 30 18 36 0 21 41 7 25 10 17 9 48 9 37 7 49 13 23 9 15 25 35 10 43 27 5 45 42 33 8 30 36 20 49 24 31 42 3 27 16 45 11 33 ...
output:
impossible
result:
ok single line: 'impossible'
Test #7:
score: 0
Accepted
time: 663ms
memory: 35020kb
input:
50 -51601 47 45 49 46 49 48 45 45 46 47 50 49 48 48 49 48 48 46 50 49 45 46 47 49 45 47 49 47 50 48 46 46 50 45 48 49 49 46 49 49 48 47 49 47 49 45 49 50 45 45 47 50 46 49 49 45 48 46 48 48 45 46 46 49 48 49 45 47 50 46 47 45 45 49 49 47 45 47 47 47 49 47 50 45 46 48 49 47 49 48 47 48 45 45 45 49 46...
output:
3319
result:
ok single line: '3319'
Test #8:
score: 0
Accepted
time: 651ms
memory: 35268kb
input:
50 1853 16 29 35 41 32 44 9 45 28 2 32 40 13 47 16 7 49 42 0 34 15 22 3 34 7 31 5 23 40 30 10 2 36 46 46 9 24 12 9 46 46 19 19 29 9 22 28 12 44 31 46 41 4 5 27 38 31 32 38 30 41 43 36 30 21 42 19 12 8 49 43 17 17 2 49 49 12 47 20 47 14 2 21 16 45 45 35 41 33 6 28 19 28 45 41 15 25 28 5 4 35
output:
2683
result:
ok single line: '2683'
Test #9:
score: 0
Accepted
time: 23ms
memory: 34996kb
input:
2 5 2 3 1 1 4
output:
9
result:
ok single line: '9'
Test #10:
score: 0
Accepted
time: 21ms
memory: 35064kb
input:
50 2303 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 49 48 0
output:
63
result:
ok single line: '63'
Test #11:
score: 0
Accepted
time: 279ms
memory: 35092kb
input:
50 -11347 0 0 30 10 0 0 15 0 13 16 34 21 0 0 23 0 2 3 43 0 0 0 41 0 0 5 0 0 10 0 26 0 0 0 0 30 12 0 0 13 0 10 0 0 1 0 38 0 5 0 0 0 0 0 0 0 28 0 0 0 29 0 12 49 26 0 0 0 0 46 10 45 49 0 0 0 29 0 30 46 30 0 17 0 39 27 0 0 0 14 27 0 0 31 0 13 0 0 23 0 29
output:
impossible
result:
ok single line: 'impossible'
Subtask #2:
score: 15
Accepted
Dependency #1:
100%
Accepted
Test #12:
score: 15
Accepted
time: 527ms
memory: 35100kb
input:
100 95010 0 83 18 41 0 95 77 84 0 20 22 0 0 0 0 0 26 50 0 1 0 54 86 34 0 0 55 0 0 38 12 42 0 28 0 0 0 1 3 24 0 96 61 0 0 70 37 0 0 15 51 0 0 0 0 69 1 0 20 7 0 49 71 0 0 0 0 0 0 0 28 62 56 0 0 23 0 71 0 0 52 42 0 0 0 0 0 87 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 77 34 0 2 0 0 0 0 64 0 0 66 0...
output:
impossible
result:
ok single line: 'impossible'
Test #13:
score: 0
Accepted
time: 36ms
memory: 35100kb
input:
100 9603 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 36 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
133
result:
ok single line: '133'
Test #14:
score: 0
Accepted
time: 1373ms
memory: 35064kb
input:
100 13237 2 100 82 74 17 71 16 3 9 27 70 61 19 42 29 96 81 11 70 51 60 41 54 34 21 6 63 50 11 97 61 77 20 97 39 36 86 10 75 35 87 20 62 4 16 42 95 97 18 75 64 62 15 94 39 44 47 23 88 80 83 1 46 40 56 83 89 14 55 29 73 53 32 71 35 67 74 91 54 19 20 19 38 40 37 64 45 65 20 56 45 96 6 47 63 72 90 10 21...
output:
10052
result:
ok single line: '10052'
Test #15:
score: 0
Accepted
time: 0ms
memory: 20360kb
input:
100 628885114412155579 51 25 68 85 83 83 60 34 62 36 34 38 35 85 41 65 56 98 63 97 94 85 39 33 34 88 24 81 10 63 42 37 69 50 72 99 10 36 97 21 2 16 46 55 73 46 40 24 55 79 64 19 31 88 3 27 61 20 46 31 6 81 76 22 80 44 37 67 75 37 58 22 83 76 52 45 85 47 49 85 60 34 79 42 26 43 95 94 36 76 55 59 70 6...
output:
impossible
result:
ok single line: 'impossible'
Test #16:
score: 0
Accepted
time: 1513ms
memory: 35184kb
input:
100 -249726 98 95 100 95 96 97 98 98 99 97 100 99 99 96 96 97 98 96 96 98 97 97 99 97 99 99 97 100 99 95 99 99 99 97 95 98 99 95 95 97 97 97 97 95 95 99 99 99 97 96 97 97 98 100 98 98 98 95 95 95 98 98 96 98 97 97 98 99 98 98 99 99 96 98 99 100 98 95 99 98 96 99 95 97 99 96 97 98 100 99 98 99 97 96 ...
output:
16659
result:
ok single line: '16659'
Test #17:
score: 0
Accepted
time: 1499ms
memory: 35184kb
input:
100 -421916 99 96 98 97 99 95 97 95 98 99 95 98 99 99 98 98 98 96 95 98 99 95 97 98 98 95 95 96 99 99 95 95 97 95 97 97 96 97 97 96 95 95 96 96 96 97 97 98 99 99 97 97 97 97 99 97 98 97 99 95 95 99 95 99 99 96 95 97 99 97 98 98 99 96 98 99 96 97 97 100 96 98 96 96 96 100 96 97 95 97 95 98 99 97 97 9...
output:
13395
result:
ok single line: '13395'
Test #18:
score: 0
Accepted
time: 21ms
memory: 35220kb
input:
100 9603 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
157
result:
ok single line: '157'
Subtask #3:
score: 10
Accepted
Test #19:
score: 10
Accepted
time: 309ms
memory: 51336kb
input:
30 38887954194235 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 444113827766 26 511237030935 22 696666627923 315938808146 20 952560827478 924020644151 850666790939 23 587888300072 23 797812801251 911390834853 677171102320 4 2 22 950650764450 278888113729 23 15 15 13 9 637120041802 20 1...
output:
5692035643249
result:
ok single line: '5692035643249'
Test #20:
score: 0
Accepted
time: 283ms
memory: 43512kb
input:
30 76226675150141 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 17 25 575187266854 933205256851 30642958327 5 723752635947 251949849516 20 241825198172 10 8 19 416001319998 846220673515 292065146547 9 17 329305181338 3 153818277782 4 622464956364 2 18 543111965233 5 20 24 8
output:
5959550686625
result:
ok single line: '5959550686625'
Test #21:
score: 0
Accepted
time: 34ms
memory: 35096kb
input:
30 783 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 842682060204 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 5 5 812222496404 0
output:
842682060231
result:
ok single line: '842682060231'
Test #22:
score: 0
Accepted
time: 292ms
memory: 51304kb
input:
30 63681107909129 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 26 29 28 25 28 162867113393 396607890615 26 27 29 27 29 29 98874364794 27 26 28 25 28 298317942689 473749524449 27 29 25 29 738708341359 378923162064 903755880355 985915633657 113061161327 29
output:
3130974862204
result:
ok single line: '3130974862204'
Test #23:
score: 0
Accepted
time: 301ms
memory: 35012kb
input:
30 1000000001687 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 999999999991 13 317621530099 581606427561 21 5 7 27 6 459097506433 15 6 29 13 29 9 25 11 10 23 17 14 6 25 11 21 10 5 16 19
output:
1000000000571
result:
ok single line: '1000000000571'
Test #24:
score: 0
Accepted
time: 192ms
memory: 43152kb
input:
30 24647168232979 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 28 25 4 19 26 4 18 66088673790 8 137263321820 624543357354 491056742273 36762815810 79008946641 16 54849098117 18 417863353158 0 0 0 0 0 22 0 0 0 1 3 21
output:
1907436309137
result:
ok single line: '1907436309137'
Test #25:
score: 0
Accepted
time: 75ms
memory: 43136kb
input:
30 50595799989746 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 22 0 6 7 969584275447 0 509040037625 0 0 717396586408 0 0 0 2 0 0 18 0 0 0 508214812962
output:
impossible
result:
ok single line: 'impossible'
Test #26:
score: 0
Accepted
time: 166ms
memory: 43116kb
input:
30 8938647816682 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 27 841672536785 8 15 6 5 2 291166519149 19 673201071629 27 23 8 14 8 0 0 0 0 0 0 16 0 0 0 0 1 4 26 0 0
output:
1806040127724
result:
ok single line: '1806040127724'
Test #27:
score: 0
Accepted
time: 19ms
memory: 35084kb
input:
30 783 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 437848852200 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 59617155335 820747192009 0
output:
437848852227
result:
ok single line: '437848852227'
Subtask #4:
score: 10
Accepted
Dependency #3:
100%
Accepted
Test #28:
score: 10
Accepted
time: 162ms
memory: 42948kb
input:
30 39213329349296 0 0 15 8 0 0 22 17 0 25 0 0 6 0 26 352775533402 821667446696 0 25 29 0 0 10 0 0 0 0 0 0 0 0 0 0 0 29 0 0 0 0 19 138752731241 0 0 423291311437 27 0 0 0 25 0 291045502006 884931905517 0 18 0 0 19 0 0 273052928628 0
output:
impossible
result:
ok single line: 'impossible'
Test #29:
score: 0
Accepted
time: 601ms
memory: 51328kb
input:
30 21923357990807 8 21 14 216923068807 26 23 20 27 21 18 23 864624580736 29 4 22 6 18 811647262759 2 7 310467930704 24 967530606906 12 15 19 246396521923 14 17 14 556793130691 12 27 7 244735599702 14 0 21 16 7 2 19 20 591091544805 198561756236 12 3 29 10 1 557855490308 733365229326 26 16 24 25 83823...
output:
7372544432312
result:
ok single line: '7372544432312'
Test #30:
score: 0
Accepted
time: 641ms
memory: 43204kb
input:
30 24025640327107 41591927263 15 16 21 8 10 802906198561 380904647313 436706099173 10 5 8 184580419211 64155825974 1 304261600343 869114876645 781473561479 988004422990 46034640463 10 11 450102275405 28 3 505693515891 18 16 2 7 976865660464 29 0 720678795261 472008146716 9459665058 784116611800 4048...
output:
13751931063415
result:
ok single line: '13751931063415'
Test #31:
score: 0
Accepted
time: 629ms
memory: 46864kb
input:
30 -131131268223581 25 922278529484 670954215509 752459272322 27 28 26 26 27 28 29 762024846326 27 329014998368 812154672454 899195298082 669278572781 633785138821 29 26 27 26 28 27 365099075657 27 778808728101 27 28 28 28 28 25 28 932917730737 312525339877 299934917805 25 29 26 25 25 29 53991889231...
output:
8619035894399
result:
ok single line: '8619035894399'
Test #32:
score: 0
Accepted
time: 645ms
memory: 49068kb
input:
30 -75220471344768 6966553994 16 617346866648 640379605383 299960157115 7 29 27 65140721600 25 24 19 359383930572 11 27 254901000693 18 453753927050 24 376770742221 23 284234709556 871513184128 260014919110 24 28 129356472928 10 9 18 6 999999999996 18 714692272298 794366028156 3 9 5 14 604803036269 ...
output:
5619722795703
result:
ok single line: '5619722795703'
Subtask #5:
score: 10
Accepted
Dependency #3:
100%
Accepted
Test #33:
score: 10
Accepted
time: 488ms
memory: 51724kb
input:
50 189795810534810 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 313141557634 32 46 6 28 887354981148 14 44 12 20 43 17 26 7 4 10 31 949343918387 49 4 24 407749755183 31 257715063142 327447392280 43 45 44 743164723251 9 18 26 30 23 245461734009...
output:
6966098559940
result:
ok single line: '6966098559940'
Test #34:
score: 0
Accepted
time: 381ms
memory: 43160kb
input:
50 162793587689945 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 28 49 10 16 181647722325 418865782618 167607836490 11023993029 46 321757623147 920049739697 6 11 924667078128 24 572740962884 17 919364419713 245267047300 26 265163915124 2385433252...
output:
8886043681855
result:
ok single line: '8886043681855'
Test #35:
score: 0
Accepted
time: 205ms
memory: 43136kb
input:
50 180427406969095 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 44 0 757097945924 747479558719 0 6 0 0 7 0 0 26 0 40 0 23 0 0 43562847026 0 521212175813 726627224608 0 0 0 163678416426 17 0 46 0 0 37 0 0 449830466494 684368...
output:
impossible
result:
ok single line: 'impossible'
Test #36:
score: 0
Accepted
time: 469ms
memory: 43376kb
input:
50 162264235060284 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 29 12 23 22 28 344376427231 42 874772962088 790393734936 306581895113 6 26 11 3 26 21 43 47 269220369454 43 5 345450372379 10 29 34 33 17 19 20 752714818476 33 45 498618944539 28 58...
output:
6534324936751
result:
ok single line: '6534324936751'
Test #37:
score: 0
Accepted
time: 518ms
memory: 51176kb
input:
50 47542388424288 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 49 48 84084484851 45 46 47 47 324104869061 11267101107 47 46 906425375031 48 48 46 45 119282476941 47 46 46 61726730293 46 647879629493 735405858271 48 45 392358979795 46 49 95217015...
output:
2918404549000
result:
ok single line: '2918404549000'
Test #38:
score: 0
Accepted
time: 517ms
memory: 35176kb
input:
50 1000000007812 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 111845393485 999999999998 18 29 204836561797 47 39 19 3 19 855441894498 179123849518 21 10 210989782789 923799603417 37 27 20 11 29 132679431725 550824570490 982033241762 30 22 7 6 35...
output:
1111845395452
result:
ok single line: '1111845395452'
Subtask #6:
score: 10
Accepted
Dependency #5:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #1:
100%
Accepted
Test #39:
score: 10
Accepted
time: 1099ms
memory: 43376kb
input:
50 -29309321968474 40 537437039951 4 23 208140731495 862903160199 717865280941 158473429202 7 4 24 21 5 7 14 392185492960 8 4 847192043475 25 2 37 44 244871588022 29 22 23 40 281940443836 28 35 40 284920678975 28 689501967713 17 38 12 43 216384338544 24 43 40 32 15 578663801902 500700624396 40 65644...
output:
12410133679545
result:
ok single line: '12410133679545'
Test #40:
score: 0
Accepted
time: 1098ms
memory: 54324kb
input:
50 -227824427223659 39 346606864040 818637860254 145921115267 96828849380 34 7864117523 45 553623746148 31 918142092761 319839208855 28 34 422409368177 2 341839318334 34 4 38 11 37 29 788597855181 98765462824 685545532844 19 6 883735029575 1 37 16 37 23355493408 48 31 40 36 15 28987724291 27 15 26 1...
output:
8430398893705
result:
ok single line: '8430398893705'
Test #41:
score: 0
Accepted
time: 1038ms
memory: 44152kb
input:
50 -84634561098753 143352277573 31 412328151558 215348397086 315708976271 641452736284 14 47 8 25 15 47 41 42 571748252743 36 12 33 37 29 127279016569 30 8 634182833257 278740763678 771183331029 32 2 36 19 36955127077 37 297606114498 3 13 22 41 32 22 6 501955772925 35 48 5 23 24 28 10 85747153484 40...
output:
10904360306368
result:
ok single line: '10904360306368'
Test #42:
score: 0
Accepted
time: 1095ms
memory: 42892kb
input:
50 -105238509005860 46 951151583371 180612870903 49 142983413718 46 862660591785 398056581577 45 354165228256 49 675718071946 150583048017 47 45 114822560399 369414039819 48 47 401412395588 120320327087 45 45 48 45 47 48 47 49 45 46 49 636719340995 45 46 49 47 793036692776 921644154981 45 48 49 48 4...
output:
15494302798313
result:
ok single line: '15494302798313'
Subtask #7:
score: 10
Accepted
Dependency #5:
100%
Accepted
Test #43:
score: 10
Accepted
time: 1069ms
memory: 51600kb
input:
100 394538310508924 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 296814641583 99 766040278887 99 98 784800424771 754434030874 95 97 98 8210609717...
output:
13654520787055
result:
ok single line: '13654520787055'
Test #44:
score: 0
Accepted
time: 973ms
memory: 43804kb
input:
100 835194212883671 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 85967827770 71 8 621187021996 836249677467 1 40 23 44 25 45 58 300454027422 59...
output:
17253748255729
result:
ok single line: '17253748255729'
Test #45:
score: 0
Accepted
time: 983ms
memory: 35528kb
input:
100 1000000062500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 27 1000000000000 36 41 311249292170 95184455669 23 14 95 67 59 146429481216 226271...
output:
1000000015680
result:
ok single line: '1000000015680'
Test #46:
score: 0
Accepted
time: 391ms
memory: 43340kb
input:
100 346290784522547 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 35 0 0 20 0 0 0 552751035545 74 0 0 20 67 0...
output:
impossible
result:
ok single line: 'impossible'
Test #47:
score: 0
Accepted
time: 1018ms
memory: 51784kb
input:
100 411650308553953 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 714899912968 626946551128 85 689747904544 912829520692 776419722685 63 78 88 368...
output:
12971397743871
result:
ok single line: '12971397743871'
Test #48:
score: 0
Accepted
time: 818ms
memory: 43672kb
input:
100 438502937700410 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 81 16 233520635985 334233650348 737756563729 24 746895710458 95 136026547109 66 ...
output:
11241469640245
result:
ok single line: '11241469640245'
Subtask #8:
score: 10
Accepted
Dependency #6:
100%
Accepted
Dependency #7:
100%
Accepted
Dependency #2:
100%
Accepted
Test #49:
score: 10
Accepted
time: 2215ms
memory: 43940kb
input:
100 -296672579719216 99 95 98 96 907424644017 95 35266592143 96 97 96 613365639535 95 97 95 95 98 97 976960633562 96 97 98 531352993407 99 98 407489970594 340132605906 96 99 96 741423081123 95 580860650994 95 713920149957 657109063071 99 822048858153 96 98 96 888925752847 97 98 95 472765812937 97 27...
output:
29985487089898
result:
ok single line: '29985487089898'
Test #50:
score: 0
Accepted
time: 2100ms
memory: 43648kb
input:
100 160313576814262 89 42 201207887113 21 58 668963461670 168267346558 63 44 877615989425 685080553621 17 31008402186 817255313584 148658889791 80 849680683338 70 50 2 87 20 15 5 640771035033 1 447239412289 30 30 26 65 27 70218329395 153685736145 628531327062 853028166269 480639186666 85 82 72 9 34 ...
output:
31700930324568
result:
ok single line: '31700930324568'
Test #51:
score: 0
Accepted
time: 2066ms
memory: 50748kb
input:
100 -835246615814208 91 43 43 439322758311 248902789767 742600274926 25 78 9 590825109670 193273357682 666032444992 22 33 20 927015958065 22 67 39 63 4 58 21 252362897527 17 69 22 608948408405 15 29 31 291670909504 560182079983 380790018475 32 30 97 68 82 383728408541 540727319494 72 91 261805365517...
output:
16861694731503
result:
ok single line: '16861694731503'
Test #52:
score: 0
Accepted
time: 2260ms
memory: 48656kb
input:
100 987888527847475 68 91 246197752863 53 552417155946 8 46 66 94 33 25 741654492141 92 9 6 53 717175313967 6 27 31 959189616224 99 10 804244243139 45 71 502974563290 45 686307753718 25 20 87 9 26 34 68 98 958269859545 293030412007 16620216594 15 10 51 98 80 34 38 90 72 104305978952 143578338499 64 ...
output:
19835785886685
result:
ok single line: '19835785886685'
Subtask #9:
score: 10
Accepted
Dependency #7:
100%
Accepted
Test #53:
score: 10
Accepted
time: 2713ms
memory: 44052kb
input:
300 6977308455072172 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
51988129888639
result:
ok single line: '51988129888639'
Test #54:
score: 0
Accepted
time: 1363ms
memory: 43992kb
input:
300 2753330070442135 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
impossible
result:
ok single line: 'impossible'
Test #55:
score: 0
Accepted
time: 42ms
memory: 35124kb
input:
300 88803 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
160908001289
result:
ok single line: '160908001289'
Test #56:
score: 0
Accepted
time: 3240ms
memory: 51864kb
input:
300 1623629946038823 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
20626558582725
result:
ok single line: '20626558582725'
Test #57:
score: 0
Accepted
time: 16ms
memory: 35020kb
input:
300 88803 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
971173945802
result:
ok single line: '971173945802'
Test #58:
score: 0
Accepted
time: 3027ms
memory: 52132kb
input:
300 5899183195616932 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
44044543118165
result:
ok single line: '44044543118165'
Test #59:
score: 0
Accepted
time: 2965ms
memory: 45096kb
input:
300 8157049043941955 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
55053569659071
result:
ok single line: '55053569659071'
Subtask #10:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Dependency #7:
100%
Accepted
Dependency #8:
100%
Accepted
Dependency #9:
100%
Accepted
Test #60:
score: 0
Time Limit Exceeded
input:
300 -4009622138313663 56 118 440945604731 38 48 133 805286558755 932833679481 161 64 16688937238 55 99 239 238 283 852433254212 130338702390 34691832465 174 278 610176006130 3 44 492059468538 281197189595 787451478244 47 536365893246 30 247 246 154 231 590547397563 151 154 35 123 216338999936 568988...