QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#179048 | #7224. The Imaginary Girlfriend | ucup-team004 | WA | 1798ms | 364908kb | C++20 | 8.5kb | 2023-09-14 17:10:45 | 2023-09-14 17:10:45 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<int> x1(n), y1(n), x2(n), y2(n);
std::vector<int> vx, vy;
vx.reserve(2 * n + 2);
vy.reserve(2 * n + 2);
for (int i = 0; i < n; i++) {
std::cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
vx.push_back(x1[i]);
vy.push_back(y1[i]);
vx.push_back(x2[i]);
vy.push_back(y2[i]);
}
int sx, sy, tx, ty;
std::cin >> sx >> sy >> tx >> ty;
vx.push_back(sx);
vy.push_back(sy);
vx.push_back(tx);
vy.push_back(ty);
if (sx == tx && sy == ty) {
std::cout << 0 << "\n";
return 0;
}
std::sort(vx.begin(), vx.end());
std::sort(vy.begin(), vy.end());
vx.erase(std::unique(vx.begin(), vx.end()), vx.end());
vy.erase(std::unique(vy.begin(), vy.end()), vy.end());
const int nx = vx.size();
const int ny = vy.size();
for (int i = 0; i < n; i++) {
x1[i] = std::lower_bound(vx.begin(), vx.end(), x1[i]) - vx.begin();
y1[i] = std::lower_bound(vy.begin(), vy.end(), y1[i]) - vy.begin();
x2[i] = std::lower_bound(vx.begin(), vx.end(), x2[i]) - vx.begin();
y2[i] = std::lower_bound(vy.begin(), vy.end(), y2[i]) - vy.begin();
}
sx = std::lower_bound(vx.begin(), vx.end(), sx) - vx.begin();
sy = std::lower_bound(vy.begin(), vy.end(), sy) - vy.begin();
tx = std::lower_bound(vx.begin(), vx.end(), tx) - vx.begin();
ty = std::lower_bound(vy.begin(), vy.end(), ty) - vy.begin();
std::map<std::array<int, 2>, int> id;
std::vector<std::array<int, 2>> ver;
std::vector<std::vector<int>> px(nx), py(ny);
std::vector<std::vector<std::array<int, 2>>> segx(nx), segy(ny);
for (int i = 0; i < n; i++) {
if (x1[i] == x2[i]) {
if (y1[i] > y2[i]) {
std::swap(y1[i], y2[i]);
}
segx[x1[i]].push_back({y1[i], y2[i]});
} else {
if (x1[i] > x2[i]) {
std::swap(x1[i], x2[i]);
}
segy[y1[i]].push_back({x1[i], x2[i]});
}
}
for (int x = 0; x < nx; x++) {
std::sort(segx[x].begin(), segx[x].end());
}
for (int y = 0; y < ny; y++) {
std::sort(segy[y].begin(), segy[y].end());
}
auto find = [&](auto &a, int x) {
auto it = std::lower_bound(a.begin(), a.end(), std::array{x + 1, 0});
if (it == a.begin()) {
return false;
}
it--;
return (*it)[1] >= x;
};
auto add = [&](int x, int y) {
if (id.count({x, y})) {
return;
}
if (!find(segx[x], y) && !find(segy[y], x)) {
return;
}
int u = id[{x, y}] = ver.size();
ver.push_back({x, y});
px[x].push_back(u);
py[y].push_back(u);
};
std::vector<int> dx{0, nx - 1};
constexpr int B = 100;
for (int i = B; i < nx; i += B) {
dx.push_back(i);
}
dx.push_back(sx);
dx.push_back(tx);
std::sort(dx.begin(), dx.end());
dx.erase(std::unique(dx.begin(), dx.end()), dx.end());
for (auto x : dx) {
for (int y = 0; y < ny; y++) {
add(x, y);
}
}
for (int i = 0; i + 1 < dx.size(); i++) {
int xl = dx[i], xr = dx[i + 1];
std::vector<int> ys;
bool first = true;
for (int y = 0; y < ny; y++) {
for (auto [l, r] : segy[y]) {
if (r < xl || l > xr) {
continue;
}
if (l <= xl && r >= xr) {
ys.push_back(y);
if (first) {
for (int x = xl; x <= xr; x++) {
add(x, y);
}
first = false;
}
} else {
for (int x = xl; x <= xr; x++) {
add(x, y);
}
if (!ys.empty()) {
for (int x = xl; x <= xr; x++) {
add(x, ys.back());
}
}
first = true;
}
}
}
if (!ys.empty()) {
for (int x = xl; x <= xr; x++) {
add(x, ys.back());
}
}
std::set<int> h;
for (auto y : ys) {
h.insert(y);
}
for (int x = xl + 1; x < xr; x++) {
for (auto [l, r] : segx[x]) {
auto itl = h.lower_bound(l + 1);
auto itr = h.lower_bound(r);
if (itl != itr) {
while (itl != itr) {
add(x, *itl);
itl = h.erase(itl);
}
itl = h.lower_bound(l);
while (itl != h.end() && *itl <= r) {
add(x, *itl);
itl++;
}
}
}
}
for (auto y : ys) {
h.insert(y);
}
for (int x = xr - 1; x > xl; x--) {
for (auto [l, r] : segx[x]) {
auto itl = h.lower_bound(l + 1);
auto itr = h.lower_bound(r);
if (itl != itr) {
while (itl != itr) {
add(x, *itl);
itl = h.erase(itl);
}
itl = h.lower_bound(l);
while (itl != h.end() && *itl <= r) {
add(x, *itl);
itl++;
}
}
}
}
}
for (int i = 0; i < n; i++) {
add(x1[i], y1[i]);
add(x2[i], y2[i]);
}
add(sx, sy);
add(tx, ty);
const int V = ver.size();
std::vector<std::array<int, 4>> adj(V);
std::vector<int> cnt(V);
std::vector<i64> dis(V, -1);
auto addEdge = [&](int u, int v) {
adj[u][cnt[u]++] = v;
adj[v][cnt[v]++] = u;
};
for (int x = 0; x < nx; x++) {
int m = px[x].size();
std::sort(px[x].begin(), px[x].end(),
[&](int i, int j) {
return ver[i][1] < ver[j][1];
});
for (int i = 0, j = 0; auto [l, r] : segx[x]) {
while (i < m && ver[px[x][i]][1] < l) {
i++;
}
while (j < m && ver[px[x][j]][1] <= r) {
j++;
}
for (int k = i; k < j - 1; k++) {
int u = px[x][k];
int v = px[x][k + 1];
addEdge(u, v);
}
}
}
for (int y = 0; y < ny; y++) {
int m = py[y].size();
std::sort(py[y].begin(), py[y].end(),
[&](int i, int j) {
return ver[i][0] < ver[j][0];
});
for (int i = 0, j = 0; auto [l, r] : segy[y]) {
while (i < m && ver[py[y][i]][0] < l) {
i++;
}
while (j < m && ver[py[y][j]][0] <= r) {
j++;
}
for (int k = i; k < j - 1; k++) {
int u = py[y][k];
int v = py[y][k + 1];
addEdge(u, v);
}
}
}
if (!id.count({sx, sy})) {
std::cout << -1 << "\n";
return 0;
}
if (!id.count({tx, ty})) {
std::cout << -1 << "\n";
return 0;
}
int S = id[{sx, sy}];
int T = id[{tx, ty}];
std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<>> q;
q.emplace(0, S);
dis[S] = 0;
while (!q.empty()) {
auto [d, x] = q.top();
q.pop();
if (dis[x] < d) {
continue;
}
for (int i = 0; i < cnt[x]; i++) {
int y = adj[x][i];
int w = std::abs(vx[ver[x][0]] - vx[ver[y][0]]) + std::abs(vy[ver[x][1]] - vy[ver[y][1]]);
if (dis[y] == -1 || dis[y] > d + w) {
dis[y] = d + w;
q.emplace(d + w, y);
}
}
}
std::cout << dis[T] << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3492kb
input:
8 0 0 0 2 0 2 2 2 2 2 2 0 2 0 0 0 -1 1 1 1 1 1 1 3 1 3 -1 3 -1 1 -1 3 2 0 -1 3
output:
6
result:
ok answer is '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
10 0 0 0 3 1 0 1 3 2 0 2 3 3 0 3 3 0 0 3 0 -1 1 4 1 -1 1 -1 10000 4 1 4 10000 -1000 10000 1000 10000 0 10000 0 5000 2 3 0 5000
output:
15005
result:
ok answer is '15005'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
19 -100000 0 100000 0 -100000 0 -100000 100000 100000 0 100000 100000 -100000 100000 100000 100000 10000 0 10000 10 -10000 0 -10000 10 10000 10 -10000 10 -10000 100000 -10000 99999 -10000 99999 -10001 99999 -10001 99999 -10001 99998 -10001 99998 -10002 99998 -10002 99998 -10002 99997 -10002 99997 -1...
output:
300015
result:
ok answer is '300015'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
19 -100000 0 100000 0 -100000 0 -100000 100000 100000 0 100000 100000 -100000 100000 100000 100000 10000 0 10000 10 -10000 0 -10000 10 10000 10 -10000 10 -10000 100000 -10000 99999 -10000 99999 -10001 99999 -10001 99999 -10001 99998 -10001 99998 -10002 99998 -10002 99998 -10002 99997 -10002 99997 -1...
output:
300015
result:
ok answer is '300015'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
200 0 0 99 0 0 1 99 1 0 2 99 2 0 3 99 3 0 4 99 4 0 5 99 5 0 6 99 6 0 7 99 7 0 8 99 8 0 9 99 9 0 10 99 10 0 11 99 11 0 12 99 12 0 13 99 13 0 14 99 14 0 15 99 15 0 16 99 16 0 17 99 17 0 18 99 18 0 19 99 19 0 20 99 20 0 21 99 21 0 22 99 22 0 23 99 23 0 24 99 24 0 25 99 25 0 26 99 26 0 27 99 27 0 28 99 ...
output:
198
result:
ok answer is '198'
Test #6:
score: 0
Accepted
time: 13ms
memory: 7032kb
input:
2000 0 0 999 0 0 1 999 1 0 2 999 2 0 3 999 3 0 4 999 4 0 5 999 5 0 6 999 6 0 7 999 7 0 8 999 8 0 9 999 9 0 10 999 10 0 11 999 11 0 12 999 12 0 13 999 13 0 14 999 14 0 15 999 15 0 16 999 16 0 17 999 17 0 18 999 18 0 19 999 19 0 20 999 20 0 21 999 21 0 22 999 22 0 23 999 23 0 24 999 24 0 25 999 25 0 2...
output:
1998
result:
ok answer is '1998'
Test #7:
score: 0
Accepted
time: 44ms
memory: 17292kb
input:
4000 0 0 1999 0 0 1 1999 1 0 2 1999 2 0 3 1999 3 0 4 1999 4 0 5 1999 5 0 6 1999 6 0 7 1999 7 0 8 1999 8 0 9 1999 9 0 10 1999 10 0 11 1999 11 0 12 1999 12 0 13 1999 13 0 14 1999 14 0 15 1999 15 0 16 1999 16 0 17 1999 17 0 18 1999 18 0 19 1999 19 0 20 1999 20 0 21 1999 21 0 22 1999 22 0 23 1999 23 0 2...
output:
3998
result:
ok answer is '3998'
Test #8:
score: 0
Accepted
time: 104ms
memory: 36488kb
input:
6000 0 0 2999 0 0 1 2999 1 0 2 2999 2 0 3 2999 3 0 4 2999 4 0 5 2999 5 0 6 2999 6 0 7 2999 7 0 8 2999 8 0 9 2999 9 0 10 2999 10 0 11 2999 11 0 12 2999 12 0 13 2999 13 0 14 2999 14 0 15 2999 15 0 16 2999 16 0 17 2999 17 0 18 2999 18 0 19 2999 19 0 20 2999 20 0 21 2999 21 0 22 2999 22 0 23 2999 23 0 2...
output:
5998
result:
ok answer is '5998'
Test #9:
score: 0
Accepted
time: 197ms
memory: 56852kb
input:
8000 0 0 3999 0 0 1 3999 1 0 2 3999 2 0 3 3999 3 0 4 3999 4 0 5 3999 5 0 6 3999 6 0 7 3999 7 0 8 3999 8 0 9 3999 9 0 10 3999 10 0 11 3999 11 0 12 3999 12 0 13 3999 13 0 14 3999 14 0 15 3999 15 0 16 3999 16 0 17 3999 17 0 18 3999 18 0 19 3999 19 0 20 3999 20 0 21 3999 21 0 22 3999 22 0 23 3999 23 0 2...
output:
3999
result:
ok answer is '3999'
Test #10:
score: 0
Accepted
time: 309ms
memory: 90760kb
input:
10000 0 0 4999 0 0 1 4999 1 0 2 4999 2 0 3 4999 3 0 4 4999 4 0 5 4999 5 0 6 4999 6 0 7 4999 7 0 8 4999 8 0 9 4999 9 0 10 4999 10 0 11 4999 11 0 12 4999 12 0 13 4999 13 0 14 4999 14 0 15 4999 15 0 16 4999 16 0 17 4999 17 0 18 4999 18 0 19 4999 19 0 20 4999 20 0 21 4999 21 0 22 4999 22 0 23 4999 23 0 ...
output:
6000
result:
ok answer is '6000'
Test #11:
score: 0
Accepted
time: 352ms
memory: 137820kb
input:
10000 0 0 4999 0 0 1 4999 1 0 2 4999 2 0 3 4999 3 0 4 4999 4 0 5 4999 5 0 6 4999 6 0 7 4999 7 0 8 4999 8 0 9 4999 9 0 10 4999 10 0 11 4999 11 0 12 4999 12 0 13 4999 13 0 14 4999 14 0 15 4999 15 0 16 4999 16 0 17 4999 17 0 18 4999 18 0 19 4999 19 0 20 4999 20 0 21 4999 21 0 22 4999 22 0 23 4999 23 0 ...
output:
-1
result:
ok answer is '-1'
Test #12:
score: 0
Accepted
time: 311ms
memory: 88732kb
input:
10000 0 0 4999 0 0 1 4999 1 0 2 4999 2 0 3 4999 3 0 4 4999 4 0 5 4999 5 0 6 4999 6 0 7 4999 7 0 8 4999 8 0 9 4999 9 0 10 4999 10 0 11 4999 11 0 12 4999 12 0 13 4999 13 0 14 4999 14 0 15 4999 15 0 16 4999 16 0 17 4999 17 0 18 4999 18 0 19 4999 19 0 20 4999 20 0 21 4999 21 0 22 4999 22 0 23 4999 23 0 ...
output:
9998
result:
ok answer is '9998'
Test #13:
score: 0
Accepted
time: 318ms
memory: 89256kb
input:
10000 0 0 4999 0 0 1 4999 1 0 2 4999 2 0 3 4999 3 0 4 4999 4 0 5 4999 5 0 6 4999 6 0 7 4999 7 0 8 4999 8 0 9 4999 9 0 10 4999 10 0 11 4999 11 0 12 4999 12 0 13 4999 13 0 14 4999 14 0 15 4999 15 0 16 4999 16 0 17 4999 17 0 18 4999 18 0 19 4999 19 0 20 4999 20 0 21 4999 21 0 22 4999 22 0 23 4999 23 0 ...
output:
1
result:
ok answer is '1'
Test #14:
score: 0
Accepted
time: 321ms
memory: 89644kb
input:
10000 0 0 4999 0 0 1 4999 1 0 2 4999 2 0 3 4999 3 0 4 4999 4 0 5 4999 5 0 6 4999 6 0 7 4999 7 0 8 4999 8 0 9 4999 9 0 10 4999 10 0 11 4999 11 0 12 4999 12 0 13 4999 13 0 14 4999 14 0 15 4999 15 0 16 4999 16 0 17 4999 17 0 18 4999 18 0 19 4999 19 0 20 4999 20 0 21 4999 21 0 22 4999 22 0 23 4999 23 0 ...
output:
6999
result:
ok answer is '6999'
Test #15:
score: 0
Accepted
time: 338ms
memory: 90240kb
input:
10000 0 0 4999 0 0 1 4999 1 0 2 4999 2 0 3 4999 3 0 4 4999 4 0 5 4999 5 0 6 4999 6 0 7 4999 7 0 8 4999 8 0 9 4999 9 0 10 4999 10 0 11 4999 11 0 12 4999 12 0 13 4999 13 0 14 4999 14 0 15 4999 15 0 16 4999 16 0 17 4999 17 0 18 4999 18 0 19 4999 19 0 20 4999 20 0 21 4999 21 0 22 4999 22 0 23 4999 23 0 ...
output:
3444
result:
ok answer is '3444'
Test #16:
score: 0
Accepted
time: 726ms
memory: 169892kb
input:
10000 0 -100000 0 23596 8 0 8 21816 18 0 18 21647 32 0 32 22755 51 0 51 24090 62 0 62 25762 75 0 75 25690 80 0 80 25172 99 0 99 22701 103 0 103 24465 113 0 113 24377 114 0 114 23874 120 0 120 21658 133 0 133 23998 136 0 136 24655 144 0 144 24588 148 0 148 26353 156 0 156 24989 166 0 166 23284 167 0 ...
output:
-1
result:
ok answer is '-1'
Test #17:
score: 0
Accepted
time: 693ms
memory: 167372kb
input:
10000 0 -100000 0 23596 8 0 8 21816 18 0 18 21647 32 0 32 22755 51 0 51 24090 62 0 62 25762 75 0 75 25690 80 0 80 25172 99 0 99 22701 103 0 103 24465 113 0 113 24377 114 0 114 23874 120 0 120 21658 133 0 133 23998 136 0 136 24655 144 0 144 24588 148 0 148 26353 156 0 156 24989 166 0 166 23284 167 0 ...
output:
252902
result:
ok answer is '252902'
Test #18:
score: 0
Accepted
time: 1625ms
memory: 329520kb
input:
10000 8158 -4495 7837 -4495 -397 -7478 -397 3130 7504 -2577 7504 -2652 2013 6377 755 6377 5949 1604 -9102 1604 -8471 -1528 -8471 5990 1902 9408 1902 -9198 -5953 3495 -5953 -4620 5657 9430 1881 9430 7889 3790 6082 3790 6509 -9526 6509 3953 -6704 -5019 -6704 4280 -5162 -3352 8454 -3352 2869 -3295 -975...
output:
1184
result:
ok answer is '1184'
Test #19:
score: 0
Accepted
time: 1474ms
memory: 307424kb
input:
10000 -4313 3855 -4313 3686 -4969 1015 -4969 -1445 -4629 -1420 -4629 472 1158 -653 -3577 -653 -1466 3829 -1899 3829 -1520 -4970 -1520 4574 -3999 1710 -3999 4256 -1202 -3153 3673 -3153 -3695 -4901 -3695 1258 -887 4460 -887 -1031 2638 1886 2638 2672 -2650 2664 -2410 2664 -2996 3096 2784 3096 744 -2078...
output:
7111
result:
ok answer is '7111'
Test #20:
score: 0
Accepted
time: 1378ms
memory: 277960kb
input:
10000 -2170 -2277 -1952 -2277 -364 -994 1373 -994 119 -1954 1785 -1954 -479 207 2445 207 -632 -176 -632 1635 -2436 2061 -2436 -1026 -1952 -1488 1962 -1488 74 1043 74 -1235 -1744 -2496 -1744 753 2319 778 2319 -2466 684 -397 684 944 2229 596 55 596 1078 -1590 1078 1012 -2259 -2072 -756 -2072 -504 -213...
output:
2140
result:
ok answer is '2140'
Test #21:
score: 0
Accepted
time: 1694ms
memory: 343768kb
input:
10000 5328 -2368 5328 11391 -15488 10013 -15488 -13741 16204 19463 16204 12899 8265 -3665 8265 6603 -3143 7482 -13860 7482 -18868 1229 -18868 5104 -5996 -3301 4384 -3301 -2169 -16062 -7948 -16062 -4676 -1245 -4676 -9882 -18363 -6529 -10350 -6529 10209 -2545 10209 15131 4254 -11754 4254 -18196 -3293 ...
output:
29574
result:
ok answer is '29574'
Test #22:
score: 0
Accepted
time: 1734ms
memory: 350556kb
input:
10000 -39351 7530 -44337 7530 -43729 -1623 -43729 19394 13752 42528 20478 42528 -29579 41446 -43975 41446 49902 -39939 -2218 -39939 -16459 39580 -16459 24843 9615 -18132 -29115 -18132 33291 8655 -28634 8655 39567 6038 -19491 6038 47795 -23496 -20844 -23496 -30598 13531 -30598 -13406 -49557 27474 -49...
output:
59489
result:
ok answer is '59489'
Test #23:
score: 0
Accepted
time: 1783ms
memory: 351524kb
input:
10000 -85664 -61700 -85664 99867 95422 20038 95422 18057 91898 -40486 14927 -40486 38244 31860 99359 31860 -59775 42827 -73804 42827 48339 -33447 92130 -33447 -13971 66025 -13971 65659 7688 -96927 -77186 -96927 -43896 -39072 -35882 -39072 -97402 89214 -15350 89214 28861 73359 28861 92069 1987 -97392...
output:
166043
result:
ok answer is '166043'
Test #24:
score: 0
Accepted
time: 1693ms
memory: 333460kb
input:
10000 -4185 4931 -4185 9055 -957 -3447 9708 -3447 4306 -8611 -3799 -8611 7938 -9662 -3454 -9662 -2030 -6055 -1067 -6055 3533 3897 1746 3897 5764 9951 5764 -6035 7178 -3198 7178 8165 -9577 6633 -7052 6633 2133 9608 2133 -5934 -7241 -2537 4939 -2537 -6343 -2783 5590 -2783 -8383 -588 -8383 -2403 -5342 ...
output:
13697
result:
ok answer is '13697'
Test #25:
score: 0
Accepted
time: 1614ms
memory: 330236kb
input:
10000 -5616 -9030 -684 -9030 7371 8296 -9818 8296 2007 1038 2007 7814 5591 -6096 -7752 -6096 -9250 -7645 -9250 2801 -9211 7265 8090 7265 6227 -7435 6227 -3303 9915 5267 9915 7897 6717 -9060 6717 -6918 -4118 2321 -1661 2321 26 4397 26 -6333 1081 -3684 6538 -3684 -590 -893 -6684 -893 3363 4069 4463 40...
output:
7344
result:
ok answer is '7344'
Test #26:
score: 0
Accepted
time: 1632ms
memory: 335124kb
input:
10000 -591 1185 -9301 1185 6739 6983 6309 6983 -4953 -2127 -4953 -8034 68 5905 6407 5905 -3392 -299 -3392 -2914 -4742 711 -4742 -4370 7230 -4244 7230 2354 3322 -4472 3322 9040 3605 8666 8715 8666 6776 -4239 6776 -9111 9895 -3088 6716 -3088 6668 7927 6668 4890 -4864 -5509 -5132 -5509 1162 -4185 1162 ...
output:
15945
result:
ok answer is '15945'
Test #27:
score: 0
Accepted
time: 1628ms
memory: 327004kb
input:
10000 -4869 -4593 -4869 -8737 3467 -4634 3467 -4642 -3060 5121 -3060 -1959 -8204 -3456 -8204 6966 5899 1924 5899 -3643 7901 -9099 -2008 -9099 9822 -1447 9822 6991 -4245 -2255 -4245 -9889 -1022 -6376 1296 -6376 9832 4014 -999 4014 371 6743 371 -9215 5333 -5690 5512 -5690 7665 -1739 7665 3301 6810 -22...
output:
11485
result:
ok answer is '11485'
Test #28:
score: 0
Accepted
time: 1551ms
memory: 328084kb
input:
10000 -1195 -496 -1195 -2622 -2197 -2911 -6283 -2911 7113 -8073 -3721 -8073 -192 -212 -8426 -212 7729 -3151 5467 -3151 2250 -2584 -3661 -2584 -7015 7604 -7015 -9970 -502 5987 7745 5987 -483 -8960 -483 -7337 3187 8247 7437 8247 757 -9569 757 457 -6242 -1178 -5069 -1178 -6470 9595 -2611 9595 -8534 585...
output:
13125
result:
ok answer is '13125'
Test #29:
score: 0
Accepted
time: 1464ms
memory: 310412kb
input:
10000 -1518 1598 -1518 2585 -4806 1513 -4806 1413 -440 3077 -2816 3077 2819 4789 -1885 4789 -1407 -2183 -1407 4559 -3826 766 406 766 4437 4058 4437 -2293 618 -2101 618 3133 3031 -1101 -2095 -1101 -231 -235 -231 -3793 -2279 4593 -2279 -215 -1230 -2670 -1810 -2670 3418 -3693 3418 4603 -1824 -4174 -182...
output:
5576
result:
ok answer is '5576'
Test #30:
score: 0
Accepted
time: 1372ms
memory: 273168kb
input:
10000 1628 -2271 1628 1528 -934 1553 -1519 1553 2273 255 2273 2030 -1072 1572 -1006 1572 -1342 -396 -1342 -1601 1293 -858 -1495 -858 -2062 1820 -2287 1820 -1524 2485 -1524 -2338 -2080 -1596 1081 -1596 -1348 507 -309 507 123 -2149 123 -1577 -2399 1849 -2399 -1992 2397 1740 -1795 1740 -577 -695 -577 4...
output:
4205
result:
ok answer is '4205'
Test #31:
score: 0
Accepted
time: 1686ms
memory: 340400kb
input:
10000 17296 -4451 17296 4192 19985 4827 19985 -2862 19343 -5136 12418 -5136 -2547 8314 -2547 -19468 -7058 18512 -7058 10530 -10460 -3341 11582 -3341 12127 -11134 15794 -11134 7017 4989 3870 4989 -11396 -3243 -8269 -3243 -11220 -7658 11040 -7658 -4270 18587 5486 18587 -16518 18986 -16518 -15160 -2503...
output:
40426
result:
ok answer is '40426'
Test #32:
score: 0
Accepted
time: 1784ms
memory: 364908kb
input:
10000 -18830 -43538 -18830 -38698 7654 12666 7654 3649 -49542 -38985 -49542 -3078 -22398 9235 -22398 23434 -20022 3314 -20022 31786 34935 19301 34935 1757 -39395 -49233 -39395 -30361 -26188 -6709 7882 -6709 -44597 32213 -44597 -32617 29448 34327 29448 21636 48662 15632 16455 15632 -47475 44266 -4747...
output:
100400
result:
ok answer is '100400'
Test #33:
score: 0
Accepted
time: 1798ms
memory: 359740kb
input:
10000 71384 91321 4192 91321 -58131 -78890 6829 -78890 -11187 65474 62707 65474 -53772 -49957 9067 -49957 12088 -74857 -49366 -74857 -12638 66156 -74394 66156 61539 -11123 50664 -11123 -60147 48454 85870 48454 95706 58827 3682 58827 -31692 59832 -66729 59832 -5295 -37887 -5295 34301 87081 -56045 964...
output:
81482
result:
ok answer is '81482'
Test #34:
score: 0
Accepted
time: 1608ms
memory: 331336kb
input:
10000 2418 -6612 2418 2340 9150 -9160 9150 1659 155 4312 155 -8748 6552 2067 6552 -7325 5893 4525 -3498 4525 6082 1998 6082 5047 -5613 -8811 -5613 936 6127 8236 6127 3177 -6822 -1798 2160 -1798 -6270 7778 -6270 -3033 -765 9868 -765 9572 -2825 -9264 4379 -9264 -4545 -5017 4146 -5017 -8043 -4641 -8043...
output:
13713
result:
ok answer is '13713'
Test #35:
score: 0
Accepted
time: 1637ms
memory: 326168kb
input:
10000 7164 -5004 3639 -5004 -399 -8022 -399 9288 -57 -6433 -3605 -6433 9427 -6336 9427 -8460 8316 -9689 8316 9341 -4276 3734 -4119 3734 -2153 2166 -2153 -5270 2845 -1494 6977 -1494 9052 1062 9052 -3980 -3433 -7873 -3433 7085 8526 5524 5329 5524 -4273 -4771 -4052 -4771 -9668 -865 -9668 -1108 -2604 68...
output:
2830
result:
ok answer is '2830'
Test #36:
score: 0
Accepted
time: 1628ms
memory: 327212kb
input:
10000 -6777 2627 -7384 2627 5618 -5900 6848 -5900 -9287 -8259 -9287 3419 -9285 -4001 -9285 5869 4663 9897 6926 9897 6763 -4673 8047 -4673 -7036 1898 -4433 1898 -7929 -9131 -7929 -8704 6219 3072 6219 -7314 2627 7137 466 7137 7223 -4946 3223 -4946 -3585 -1969 -7706 -1969 -9425 9878 -9924 9878 262 -260...
output:
21394
result:
ok answer is '21394'
Test #37:
score: 0
Accepted
time: 1649ms
memory: 331008kb
input:
10000 559 6777 559 7719 -6565 5438 -6565 9257 5625 -8431 5625 7954 -9661 5750 -8445 5750 7851 862 114 862 -7782 -3783 -7782 7827 2905 -1916 2905 9085 3491 4846 7441 4846 4522 4640 3164 4640 8073 6678 8073 -9568 6388 -7703 6388 367 -6904 -4771 -55 -4771 -8523 -1944 -8523 3030 -5030 -785 -5030 356 -70...
output:
9109
result:
ok answer is '9109'
Test #38:
score: 0
Accepted
time: 1772ms
memory: 354564kb
input:
10000 -44051 72925 -40788 72925 68102 -29000 -35187 -29000 40838 -582 4699 -582 49325 31476 49325 -681 -9685 33684 -13288 33684 52844 14063 52844 76608 93980 44245 93980 -8857 74422 66280 74422 -73782 -83307 -14255 -83307 61723 -10595 25726 -10595 -9216 -53992 4481 20063 4481 85619 -53789 85619 -979...
output:
79661
result:
ok answer is '79661'
Test #39:
score: 0
Accepted
time: 638ms
memory: 146072kb
input:
9997 -1 0 -3035 0 -1 1 -6061 1 -1 2 -4277 2 -1 3 -2275 3 -1 4 -2216 4 -1 5 -4401 5 -1 6 -11104 6 -1 7 -9973 7 -1 8 -9519 8 -1 9 -9804 9 -1 10 -3794 10 -1 11 -6541 11 -1 12 -6950 12 -1 13 -4012 13 -1 14 -7541 14 -1 15 -10224 15 -1 16 -2111 16 -1 17 -6189 17 -1 18 -8113 18 -1 19 -7672 19 -1 20 -9342 2...
output:
209994
result:
ok answer is '209994'
Test #40:
score: 0
Accepted
time: 10ms
memory: 4956kb
input:
4630 94606 -99989 94264 -99989 92379 -99989 92181 -99989 84390 -99989 86271 -99989 74063 -99989 72527 -99989 63891 -99989 69168 -99989 60250 -99989 53604 -99989 50668 -99989 52733 -99989 49455 -99989 49073 -99989 48186 -99989 37337 -99989 36191 -99989 31703 -99989 22687 -99989 25138 -99989 21912 -99...
output:
390641
result:
ok answer is '390641'
Test #41:
score: 0
Accepted
time: 6ms
memory: 4804kb
input:
1710 68322 -95430 95409 -95430 52698 -95430 67671 -95430 49968 -95430 7400 -95430 -16103 -95430 3247 -95430 -18656 -95430 -17887 -95430 -49221 -95430 -20825 -95430 -49982 -95430 -77043 -95430 -82232 -95430 -79179 -95430 -97652 -95430 -83012 -95430 72892 -93674 95409 -93674 59969 -93674 69789 -93674 ...
output:
25193
result:
ok answer is '25193'
Test #42:
score: 0
Accepted
time: 324ms
memory: 68248kb
input:
7178 19249 -82086 19249 -99809 48091 -94976 48091 53479 70447 -99809 70447 -77463 -99567 -32219 -50088 -32219 -93156 -50534 -93156 60093 65212 88727 65212 96022 -29752 -20300 -29752 -99809 -60328 -99809 -60328 -37600 -39165 -74243 -87672 -74243 51374 45613 51374 27542 -99567 -28919 -61920 -28919 -42...
output:
52083
result:
ok answer is '52083'
Test #43:
score: 0
Accepted
time: 263ms
memory: 59612kb
input:
9173 -41428 -52844 -27987 -52844 10986 45134 -3466 45134 90186 98952 90186 -98329 -47358 98952 -47358 79344 1815 -12391 1815 98952 -42571 98952 -42571 60381 47955 -98329 47955 98952 94398 -98329 94398 98952 27389 -74243 99983 -74243 -16856 98952 -16856 70779 -98561 -98329 -98561 76935 26755 -66593 2...
output:
143743
result:
ok answer is '143743'
Test #44:
score: -100
Wrong Answer
time: 41ms
memory: 12524kb
input:
7986 28969 65753 28969 65322 -90260 -90828 99442 -90828 25439 77057 25439 76935 -90260 -67337 99442 -67337 99442 10771 -90260 10771 -90260 15577 99442 15577 -90260 -34312 99442 -34312 99442 -35605 12318 -35605 -90260 -38561 99442 -38561 -32519 -57589 -32519 -50328 99442 59859 56307 59859 -90260 5827...
output:
293786
result:
wrong answer expected '281434', found '293786'