QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#120621 | #1154. Wombats | Qwerty1232# | 76 | 3703ms | 104936kb | C++17 | 3.8kb | 2023-07-07 01:29:34 | 2024-05-26 02:56:50 |
Judging History
answer
#pragma GCC optimize("O3")
#include "wombats.h"
#include <bits/stdc++.h>
constexpr int inf = 1e9 + 1;
int n, m;
struct Cum {
std::vector<int> L;
std::vector<std::vector<int>> data;
std::vector<std::vector<int>> v, h;
int len;
Cum() {
len = 0;
}
Cum(std::vector<int> v, std::vector<int> h) {
assert(v.size() == m);
assert(h.size() == m - 1);
len = 1;
L = v;
this->v.push_back(v);
this->h.push_back(h);
return;
std::vector<int> ph(m);
std::partial_sum(h.begin(), h.end(), ph.begin() + 1);
data.assign(m, std::vector<int>(m));
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
data[i][j] = abs(ph[i] - ph[j]);
}
}
}
};
Cum fuck(Cum a) {
if (a.len == -1) {
return a;
}
int l = a.len;
Cum res;
res.len = -1;
res.data.resize(m);
res.L = a.L;
for (int i = 0; i < m; i++) {
std::vector<int> dp(m, inf);
dp[i] = 0;
auto shit = [&](auto& h) {
for (int j = 1; j < m; j++) {
dp[j] = std::min(dp[j], dp[j - 1] + h[j - 1]);
}
for (int j = m - 2; j >= 0; j--) {
dp[j] = std::min(dp[j], dp[j + 1] + h[j]);
}
};
shit(a.h[0]);
for (int j = 1; j < l; j++) {
for (int t = 0; t < m; t++) {
dp[t] += a.v[j][t];
}
shit(a.h[j]);
}
res.data[i] = dp;
}
return res;
}
Cum merge(Cum a, Cum b) {
if (!a.len || !b.len) {
return a.len ? a : b;
}
// a = fuck(a);
// b = fuck(b);
if (a.len == -1 || b.len == -1) {
if (a.len != -1) {
a = fuck(a);
}
if (b.len != -1) {
b = fuck(b);
}
} else {
a.len += b.len;
a.v.insert(a.v.end(), b.v.begin(), b.v.end());
a.h.insert(a.h.end(), b.h.begin(), b.h.end());
if (a.len > 50) {
a = fuck(a);
}
return a;
}
Cum res;
res.len = -1;
res.L = a.L;
res.data.assign(m, std::vector<int>(m, inf));
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
for (int t = 0; t < m; t++) {
res.data[i][t] = std::min(res.data[i][t], a.data[i][j] + b.L[j] + b.data[j][t]);
}
}
}
return res;
}
std::vector<std::vector<int>> h, v;
int size;
std::vector<Cum> data;
void build() {
for (size = 1; size < n; size *= 2)
;
data.resize(2 * size);
for (int i = 0; i < n; i++) {
data[size + i] = Cum(v[i], h[i]);
}
for (int i = size - 1; i > 0; i--) {
data[i] = merge(data[2 * i], data[2 * i + 1]);
}
}
void update(int i) {
data[i + size] = Cum(v[i], h[i]);
i += size;
for (i >>= 1; i > 0; i >>= 1) {
data[i] = merge(data[2 * i], data[2 * i + 1]);
}
}
void init(int r, int c, int H[5000][200], int V[5000][200]) {
n = r;
m = c;
h.assign(n, std::vector<int>(m - 1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
h[i][j] = H[i][j];
}
}
v.assign(n, std::vector<int>(m));
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
v[i + 1][j] = V[i][j];
}
}
build();
}
void changeH(int p, int q, int w) {
h[p][q] = w;
update(p);
}
void changeV(int p, int q, int w) {
v[p + 1][q] = w;
update(p + 1);
}
int escape(int v1, int v2) {
if (data[1].len != -1) {
data[1] = fuck(data[1]);
}
int res = data[1].data[v1][v2];
return res;
// return 42;
}
詳細信息
Subtask #1:
score: 9
Accepted
Test #1:
score: 9
Accepted
time: 8ms
memory: 14232kb
input:
5000 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 500 lines
Test #2:
score: 0
Accepted
time: 12ms
memory: 13784kb
input:
4999 1 447 741 689 474 539 506 732 156 94 221 858 311 318 930 146 187 13 881 960 441 480 653 504 999 274 251 772 626 944 822 314 881 695 235 952 241 204 347 821 392 641 146 316 410 305 658 977 748 363 387 550 611 991 287 105 927 679 460 660 952 310 680 669 697 768 30 25 979 743 20 624 174 877 928 46...
output:
2499534 2499661 2499736 2499923 2500085 2500946 2501218 2501738 2501625 2501253 2501148 2501154 2501273 2501617 2501635 2501466 2501560 2500971 2501220 2500994 2501607 2502361 2502491 2502352 2502386 2502494 2502289 2502643 2502459 2502771 2502603 2502938 2503119 2503397 2503204 2503545 2503698 2504...
result:
ok 500 lines
Test #3:
score: 0
Accepted
time: 40ms
memory: 13368kb
input:
5000 1 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 100...
output:
4998997 4998991 4998988 4998980 4998976 4998973 4998964 4998956 4998948 4998943 4998940 4998934 4998931 4998931 4998926 4998923 4998920 4998910 4998901 4998893 4998887 4998879 4998876 4998869 4998862 4998853 4998849 4998845 4998844 4998837 4998831 4998822 4998816 4998813 4998806 4998803 4998800 4998...
result:
ok 200000 lines
Test #4:
score: 0
Accepted
time: 12ms
memory: 11988kb
input:
5000 1 433 848 657 828 954 990 864 392 35 901 873 848 527 3 10 323 871 76 674 920 258 988 801 609 433 352 603 381 683 573 25 725 353 168 801 379 735 424 34 30 843 683 987 47 745 150 974 935 557 6 13 517 660 467 324 945 274 131 510 937 19 405 11 672 269 126 814 909 957 994 394 475 181 35 266 532 873 ...
output:
2499408 2498889 2499588 2498991 2499260 2499709 2499733 2500114 2499563 2498935 2498612 2499139 2499488 2500139 2500428 2500261 2500327 2500510 2500801 2501354 2501370 2501004 2500428 2499903 2499517 2499976 2499251 2499194 2499490 2499101 2498337 2498687 2498284 2498699 2498626 2499077 2498688 2498...
result:
ok 500 lines
Test #5:
score: 0
Accepted
time: 12ms
memory: 13620kb
input:
5000 1 659 643 470 768 565 843 606 284 30 676 657 185 435 404 783 107 920 788 958 243 887 609 726 930 344 543 337 712 77 155 681 336 441 514 611 888 345 433 469 169 686 249 545 449 936 423 168 808 773 249 632 125 528 980 611 647 524 596 152 126 424 542 916 108 619 428 38 292 540 921 3 528 510 40 521...
output:
2494309 2494050 2493903 2493892 2493169 2493654 2493478 2493008 2493414 2492936 2492559 2492957 2492633 2492359 2491789 2491386 2491399 2491044 2491066 2491938 2492119 2492434 2492918 2492891 2492211 2492268 2491911 2491890 2492480 2493111 2493123 2493446 2493919 2494189 2494465 2494064 2494270 2494...
result:
ok 500 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
2 1 0 1 3 0 0
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
2 1 1 1 3 0 0
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
2 1 1000 1 3 0 0
output:
1000
result:
ok single line: '1000'
Subtask #2:
score: 12
Accepted
Test #9:
score: 12
Accepted
time: 1ms
memory: 5916kb
input:
20 20 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 ...
output:
2 3 4 2 2 2 3 3 2 2 3 4 4 3 3 3 2 2 5 2 4 2 3 3 2 4 2 2 3 3 2 2 3 3 3 2 2 4 2 2 4 2 4 2 2 3 2 2 3 3 2 4 3 3 4 2 3 3 2 3 3 2 2 2 3 4 2 5 3 3 2 2 4 4 2 2 3 4 3 2 2 3 2 2 2 2 3 2 2 4 3 4 2 2 4 4 3 2 3 3 3 2 2 2 3 3 4 2 2 2 2 1 2 2 2 2 3 2 3 3 1 4 3 1 4 2 2 3 2 3 3 3 3 2 2 2 3 3 3 3 3 2 2 3 2 3 4 2 3 2 ...
result:
ok 400 lines
Test #10:
score: 0
Accepted
time: 1ms
memory: 5920kb
input:
20 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 400 lines
Test #11:
score: 0
Accepted
time: 1ms
memory: 5924kb
input:
20 20 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000...
output:
21000 29000 29000 31000 22000 19000 28000 26000 26000 28000 26000 26000 25000 21000 33000 25000 26000 25000 28000 22000 20000 28000 25000 32000 22000 30000 24000 20000 19000 28000 24000 23000 24000 28000 26000 24000 34000 34000 32000 36000 22000 33000 20000 21000 28000 30000 20000 34000 30000 20000 ...
result:
ok 400 lines
Test #12:
score: 0
Accepted
time: 1ms
memory: 5924kb
input:
20 20 2 1 2 1 1 2 1 1 2 2 2 2 1 1 2 1 1 2 1 1 2 2 1 1 1 2 1 2 1 1 2 1 1 2 1 2 2 2 1 2 2 1 1 2 1 2 1 1 2 2 1 2 1 1 1 1 1 2 1 2 2 2 2 2 1 2 2 1 1 2 1 1 1 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 1 2 1 2 1 2 2 1 2 2 2 1 1 1 2 2 2 1 2 2 1 2 2 1 2 2 1 1 2 1 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 2 1 2 2 2 2 2 2 2 ...
output:
562 572 574 567 546 553 550 542 561 571 581 553 540 586 574 565 573 554 569 555 585 569 559 567 548 552 552 562 574 562 568 567 565 544 564 555 571 553 574 555 567 562 537 560 561 565 559 577 567 580 555 587 563 584 548 578 559 551 565 563 559 576 548 581 553 565 567 583 580 548 557 555 559 559 553 ...
result:
ok 400 lines
Test #13:
score: 0
Accepted
time: 1ms
memory: 5928kb
input:
19 19 425 921 827 377 249 290 640 661 631 355 363 244 490 25 748 341 106 212 523 855 471 10 474 731 49 296 604 576 543 984 846 867 181 76 627 158 451 542 210 680 814 303 531 240 199 941 819 731 586 689 312 726 469 665 892 384 999 986 193 953 766 294 630 559 546 293 860 304 469 849 599 16 810 792 758...
output:
8147 6666 6372 7827 6601 6424 6549 6490 6987 7460 6022 7025 5924 7227 8731 7188 6795 6725 7388 7042 9074 6202 6649 7989 7203 6233 7303 8121 6751 6447 7169 6302 9504 7198 7047 5744 6763 6598 7201 7467 7410 6870 6155 7083 7491 7208 7039 8133 7113 6607 8026 6663 7166 8894 6311 8712 6713 6686 9617 7044 ...
result:
ok 361 lines
Test #14:
score: 0
Accepted
time: 1ms
memory: 5868kb
input:
19 20 430 918 707 686 598 149 947 147 975 644 266 544 10 224 265 543 192 876 952 948 472 903 188 71 788 379 275 880 130 108 849 373 698 963 366 40 422 581 602 329 210 216 564 765 828 67 174 37 923 104 480 692 85 613 391 673 745 562 395 386 748 765 266 989 741 488 211 234 621 698 501 887 143 901 835 ...
output:
8452 7046 7922 6380 8369 7800 7447 6220 7048 8363 6411 6745 7168 8170 7942 7025 8240 8962 6733 6743 8074 6251 7606 7465 6663 7049 6659 9750 6275 9837 7292 7874 7301 7570 6349 9832 8701 8264 6641 8660 8095 7425 7777 8968 6501 7616 7759 7219 6516 7456 6869 6751 7239 7969 6876 7351 6277 7938 6070 7839 ...
result:
ok 400 lines
Test #15:
score: 0
Accepted
time: 1ms
memory: 6180kb
input:
20 19 585 272 917 550 377 835 7 575 506 106 544 322 850 948 561 986 352 911 273 542 609 310 567 309 490 297 472 555 649 21 402 370 27 783 131 763 193 704 61 199 657 897 511 779 362 987 943 138 476 34 537 290 189 436 238 791 624 980 255 647 716 673 937 61 366 167 60 557 742 63 178 589 49 154 682 72 3...
output:
8788 7928 8141 7603 6336 8649 7382 7013 5974 6363 7810 5456 7984 7212 7439 7233 8064 7188 6021 7417 5966 6657 7565 8081 7964 5275 6605 5439 6353 6545 5505 5956 7412 7720 5628 6854 7491 5336 7558 6690 4761 7365 7864 8450 6203 6117 7863 6866 7505 6968 6742 8092 7471 6964 7112 7353 7824 4769 7858 7153 ...
result:
ok 361 lines
Test #16:
score: 0
Accepted
time: 36ms
memory: 5984kb
input:
20 20 171 782 955 632 436 974 641 635 587 708 772 208 970 668 432 709 422 992 410 260 436 695 810 846 290 873 449 690 905 150 273 750 872 229 151 83 196 309 512 185 689 443 751 172 731 287 731 702 743 333 922 960 523 688 235 288 572 764 493 223 166 113 980 993 978 795 928 248 654 430 340 20 764 529 ...
output:
9126 8026 7187 6713 7119 8676 7271 8586 6239 7982 6697 10252 7327 6535 8061 7604 6069 8298 8471 7697 6836 9035 7530 8740 7928 7754 6091 7609 6959 7575 7154 7306 6298 8432 6907 7325 8316 7464 9250 7160 8134 8906 6903 7909 9132 7244 6240 6502 7522 8061 10174 6953 8335 5286 10079 8521 6812 6873 7683 72...
result:
ok 200000 lines
Test #17:
score: 0
Accepted
time: 1ms
memory: 5928kb
input:
20 20 0 1 5 0 1 2 3 2 3 1 4 2 2 0 4 0 2 4 2 4 3 4 1 4 2 2 1 0 0 4 3 5 2 5 4 5 4 0 0 1 2 0 2 2 3 3 1 0 4 3 5 5 2 2 0 3 3 5 0 1 0 4 1 5 5 3 3 1 1 5 0 1 4 4 4 1 2 1 3 1 3 4 5 4 3 2 0 1 5 3 3 0 5 0 2 1 3 4 5 3 2 2 4 5 0 2 1 3 4 1 5 4 0 2 5 3 3 3 5 2 4 1 5 1 2 4 2 5 0 3 2 4 2 0 4 0 4 3 5 1 2 2 3 5 0 2 4 ...
output:
4115 4147 4149 4149 4159 4136 4123 4156 4135 4135 4112 4137 4160 4137 4155 4125 4127 4126 4110 4126 4130 4131 4157 4116 4126 4151 4153 4120 4132 4122 4128 4157 4146 4122 4127 4122 4137 4137 4121 4159 4131 4136 4168 4116 4124 4135 4142 4136 4164 4156 4115 4135 4117 4158 4136 4113 4131 4162 4120 4167 ...
result:
ok 400 lines
Subtask #3:
score: 16
Accepted
Test #18:
score: 16
Accepted
time: 153ms
memory: 6864kb
input:
99 100 278 927 579 441 245 179 75 110 797 424 854 825 213 194 8 666 556 81 205 126 225 882 913 85 319 94 784 83 486 391 262 251 623 746 706 453 842 242 414 876 885 88 175 334 971 539 90 860 11 32 402 776 314 301 966 800 744 20 777 681 535 55 191 1 773 503 55 223 285 3 136 505 644 175 686 454 2 818 3...
output:
34137 33138 37910 32392 41254 32247 38531 34081 37360 34438 33135 35264 34338 34274 32817 37400 34342 33179 40496 33261 41994 47098 31641 38823 37198 40566 33034 32817 34700 38109 35872 39102 34870 32419 37001 46881 35325 36446 32885 36366 31624 38905 36690 36551 33236 33300 33124 33854 32755 31817 ...
result:
ok 100 lines
Test #19:
score: 0
Accepted
time: 261ms
memory: 6932kb
input:
99 99 1 1 2 2 1 2 2 2 2 1 1 1 2 1 2 1 2 1 2 1 2 1 1 2 1 1 1 1 1 1 1 1 2 1 2 2 1 2 1 2 2 1 1 2 2 1 1 2 2 2 2 2 1 2 1 1 2 1 2 1 1 1 1 2 1 2 1 1 2 1 1 2 1 1 1 2 1 2 1 2 2 2 1 1 1 1 2 2 2 1 2 1 1 1 1 2 1 2 2 2 1 2 1 1 1 2 2 2 2 2 1 1 1 2 1 1 1 1 2 1 1 1 2 1 2 1 2 2 1 1 2 1 1 1 1 2 1 1 2 1 2 2 1 1 1 2 2 ...
output:
411 420 286 382 419 247 300 380 380 464 362 270 467 349 404 334 463 355 299 287 277 305 391 334 399 320 403 421 380 429 477 472 420 402 361 347 336 291 318 446 384 434 413 414 379 479 415 368 449 406 278 255 354 469 334 369 373 386 384 377 379 474 406 317 422 387 328 352 369 385 384 496 414 322 327 ...
result:
ok 100 lines
Test #20:
score: 0
Accepted
time: 240ms
memory: 6864kb
input:
100 100 771 563 536 329 511 849 894 145 20 322 809 505 564 428 381 982 110 168 990 198 657 343 219 117 413 9 275 82 377 448 244 303 50 189 712 467 0 976 732 661 138 15 322 345 5 43 296 497 658 197 239 741 552 296 300 250 80 869 322 674 930 90 53 876 992 359 83 878 142 742 711 337 62 926 669 400 669 ...
output:
38171 40554 36621 33257 33092 38503 35045 32577 32429 43919 32703 34764 34210 35608 32902 35864 49580 34069 34994 41144 35699 30269 43923 37719 33127 32469 34795 34055 43581 36110 32467 39176 35390 35117 37346 31965 39083 30180 32697 36738 33888 33593 38409 45030 37544 35087 35710 32800 38298 36617 ...
result:
ok 100 lines
Test #21:
score: 0
Accepted
time: 227ms
memory: 6972kb
input:
100 100 814 802 706 373 454 999 307 489 576 423 899 639 301 848 216 405 635 487 96 960 489 845 244 657 384 569 521 819 68 26 744 675 356 558 465 137 918 352 275 936 726 631 671 30 943 157 472 450 526 730 705 786 217 433 968 12 267 395 100 321 887 315 61 902 975 378 533 240 249 358 956 636 516 172 74...
output:
34653 40263 39295 33532 34944 37747 39041 41981 35600 33945 37565 34112 32838 46605 35853 38666 33967 44621 32048 39149 39056 34531 42043 34135 33912 35918 34282 34055 35873 43095 37421 37318 34804 35401 35184 34022 35833 36120 37379 34706 34245 33838 36998 40575 43444 39228 40523 36621 34578 40214 ...
result:
ok 100 lines
Test #22:
score: 0
Accepted
time: 263ms
memory: 6980kb
input:
100 99 208 377 351 287 823 716 294 250 82 218 240 646 445 280 388 127 574 49 286 393 326 834 220 867 791 862 541 253 211 10 488 330 642 313 122 739 74 76 456 482 332 523 812 421 371 83 133 717 668 118 578 856 525 993 510 500 420 61 464 415 824 926 156 601 267 46 306 86 213 336 455 491 231 586 596 55...
output:
34715 35897 35518 31961 31281 36070 33244 35414 36872 41196 34262 38837 37301 46758 45692 34800 47096 38282 35932 32251 33657 32583 34268 43772 32509 41391 37289 34407 39661 32725 35655 34759 38997 34770 38358 37026 31981 30645 33554 33081 33371 33345 34853 36933 34624 32412 38065 38133 34037 31482 ...
result:
ok 100 lines
Test #23:
score: 0
Accepted
time: 1340ms
memory: 6964kb
input:
100 100 2 2 2 1 2 2 2 2 1 1 1 1 1 2 2 1 2 1 2 2 2 1 2 1 2 1 2 1 1 1 1 2 2 2 2 1 1 1 1 2 1 2 1 2 2 2 1 1 2 2 1000 2 2 2 1 2 2 2 2 1 1 1 2 1 1 1 2 2 2 2 1 2 2 1 2 1 1 1 1 1 2 1 1 2 1 2 2 2 2 2 2 2 2 2 1 2 1 1 1 1 2 2 1 1 1 2 2 2 2 1 1 2 1 2 2 2 2 2 1 2 1 1 1 1 1 1 1 2 2 1 1 2 2 2 1 1 1 2 2 1 2 1 2 1 2...
output:
8856 9552 9544 8546 8816 9396 8969 9549 8642 8229 8795 8382 9624 9367 10599 10342 9479 9066 10323 9910 9162 8903 9315 9056 8290 8031 8443 8184 8434 8175 8587 8328 9129 8851 9973 9695 10104 10846 9958 10700 9926 10659 9785 10518 9926 10659 9785 10518 10777 10530 10771 10524 10913 10666 10907 10660 11...
result:
ok 100 lines
Test #24:
score: 0
Accepted
time: 1ms
memory: 6168kb
input:
3 4 0 2 5 7 1 1 0 4 0 0 0 0 2 0 3 4 7 5 3 2 1 3 3 3 2 0 0 5 1 1 1 6 3 2 1
output:
2 7 5
result:
ok 3 lines
Subtask #4:
score: 18
Accepted
Test #25:
score: 18
Accepted
time: 19ms
memory: 17368kb
input:
4999 2 57 194 293 623 704 290 534 103 734 55 774 398 571 972 268 57 567 207 425 914 855 650 38 540 496 242 353 263 889 192 216 416 414 54 80 451 456 956 809 169 909 394 244 936 77 180 653 263 338 732 752 739 250 759 738 450 431 243 50 897 790 606 389 146 148 878 611 707 802 623 187 98 653 244 127 75...
output:
2116460 2116711 2116513 2116650 2116456 2116707 2116650 2116513 2116707 2116456 2116508 2116645 2116508 2116645 2116750 2116613 2116613 2116750 2116613 2116750 2116868 2116617 2116540 2116677 2116540 2116677 2116540 2116677 2116483 2116734 2116353 2116216 2116216 2116353 2116353 2116216 2116159 2116...
result:
ok 1000 lines
Test #26:
score: 0
Accepted
time: 16ms
memory: 17388kb
input:
5000 2 1 2 1 2 1 1 1 1 1 2 2 1 1 2 1 1 1 2 2 1 1 1 1 1 1 2 2 2 2 2 1 1 1 2 1 1 1 1 1 2 2 1 1 1 2 1 2 2 1 1 1 2 2 2 1 2 1 2 1 1 2 2 1 1 1 1 2 1 1 2 2 1 2 2 2 1 2 2 2 2 1 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 1 1 2 1 1 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 1 2 1 1 1 2 1 1 2 1 2 1 1 1 2 1 1 2 2 1 1 2 1 1...
output:
12487 12489 12483 12485 12479 12481 12478 12476 12474 12474 12472 12474 12470 12470 12468 12470 12463 12465 12463 12463 12459 12457 12457 12457 12454 12452 12452 12452 12447 12447 12447 12445 12443 12441 12437 12439 12435 12433 12433 12433 12431 12429 12428 12430 12425 12425 12423 12421 12418 12420 ...
result:
ok 1000 lines
Test #27:
score: 0
Accepted
time: 20ms
memory: 17184kb
input:
5000 2 173 567 56 565 753 213 961 385 872 123 905 615 516 903 116 211 127 236 976 686 60 232 391 414 16 543 239 309 349 745 40 211 205 356 547 380 467 1 85 662 46 16 529 245 599 157 383 815 668 412 895 443 659 478 745 20 374 923 414 429 368 760 499 145 900 153 602 449 378 669 122 664 408 687 949 306...
output:
2136683 2136758 2136481 2136752 2136481 2136752 2136579 2136654 2136481 2136752 2136579 2136654 2136579 2136654 2136481 2136752 2136873 2136602 2136602 2136873 2136694 2136769 2137398 2137323 2137496 2137225 2137109 2137380 2137282 2137207 2137380 2137109 2137380 2137109 2137282 2137207 2137109 2137...
result:
ok 1000 lines
Test #28:
score: 0
Accepted
time: 32ms
memory: 17368kb
input:
5000 2 813 963 394 766 58 543 997 578 576 766 668 242 47 7 840 419 7 550 834 572 275 39 805 152 181 95 32 380 494 521 64 32 771 689 605 514 980 899 247 759 37 151 304 502 28 347 922 763 249 828 119 217 677 52 940 912 458 609 231 544 698 901 524 680 481 519 590 245 495 664 616 825 151 343 796 14 261 ...
output:
2124406 2124123 2124064 2124465 2124123 2124406 2124465 2124064 2124465 2124064 2124123 2124406 2124064 2124465 2124406 2124123 2124465 2124064 2124123 2124406 2124406 2124123 2124406 2124123 2124064 2124465 2124465 2124064 2124064 2124465 2124465 2124064 2124465 2124064 2124465 2124064 2124123 2124...
result:
ok 100000 lines
Subtask #5:
score: 21
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #29:
score: 21
Accepted
time: 2985ms
memory: 54376kb
input:
5000 100 2 1 2 2 2 2 1 1 1 1 1 2 2 2 2 2 1 2 1 1 2 1 1 2 2 1 1 1 1 1 1 2 1 1 1 2 1 1 2 1 2 1 2 2 1 2 2 1 1 1 1000 2 2 1 1 2 1 1 1 1 1 1 1 2 1 2 1 1 1 1 2 1 2 2 2 1 1 1 1 2 1 2 2 2 1 1 1 2 1 1 2 2 1 2 2 1 2 2 2 2 1 1 2 2 1 1 1 2 2 1 1 2 1 2 2 1 1 2 1 1 1 2 1 2 2 1 2 2 2 1 2 2 2 2 1 1 1 2 1 2 1 2 2 2 ...
output:
436928 435886 436992 434928 435980 435949 436957 436938 435973 435955 436950 435962 435921 435938 434986 435980 436923 435970 434968 434974 435953 434955 435932 434925 435942 434940 435992 434987 434951 435986 435949 435967 436978 435971 436984 436995 434974 436980 435976 435961 436001 435899 436932...
result:
ok 50000 lines
Test #30:
score: 0
Accepted
time: 3231ms
memory: 45572kb
input:
4095 100 481 484 181 501 792 565 922 359 219 729 209 968 974 498 52 422 273 884 705 780 608 140 255 301 450 778 20 660 470 721 995 522 183 373 658 965 286 913 453 352 606 706 889 285 336 386 643 449 879 278 924 316 938 197 40 608 350 322 896 880 762 81 740 685 169 770 597 192 406 554 400 672 145 727...
output:
1303643 1303152 1306077 1305891 1306384 1300171 1306516 1306449 1307163 1306160 1302547 1302527 1302293 1304213 1300982 1302398 1303731 1305884 1302862 1306413 1300734 1306621 1304996 1306544 1305017 1301285 1306219 1305306 1301337 1307787 1302978 1306355 1302732 1306026 1307255 1303162 1305431 1300...
result:
ok 50000 lines
Test #31:
score: 0
Accepted
time: 3632ms
memory: 46340kb
input:
4097 100 869 505 763 939 265 707 491 836 623 379 506 939 944 275 846 645 613 28 689 135 238 424 384 447 556 978 633 849 920 983 173 619 707 451 928 418 893 783 714 758 248 827 483 794 459 593 823 960 808 856 926 694 628 588 864 884 712 956 656 672 722 290 309 864 996 804 977 750 876 854 652 915 400 ...
output:
990177 991605 993970 991434 990415 993173 995922 994042 988903 991623 991428 994157 995104 987758 992544 992784 996536 992309 994793 992673 997246 997684 997959 1000648 997867 993744 994131 989941 991246 988479 995408 993856 994487 993073 997515 991655 997453 992371 991412 990621 993475 991019 99436...
result:
ok 50000 lines
Test #32:
score: 0
Accepted
time: 3703ms
memory: 54428kb
input:
5000 100 0 5 0 5 2 1 3 1 1 1 1 3 4 5 0 4 0 5 4 1 1 2 2 1 4 5 4 5 0 1 4 4 3 0 2 4 0 0 1 2 1 3 0 4 2 0 3 5 2 1 1 0 4 3 2 3 0 0 3 5 1 0 4 0 2 4 5 5 1 3 1 5 2 2 3 3 5 0 2 2 2 4 1 2 5 0 4 3 1 5 1 1 4 2 4 4 4 0 0 1 3 0 4 1 0 0 4 1 2 0 2 1 2 4 5 0 3 2 5 1 1 3 5 0 2 3 5 5 5 1 1 3 4 0 2 3 0 0 2 2 3 3 1 5 0 1...
output:
693215 693020 693076 693063 693113 693200 693145 693058 693234 693101 693152 693072 693040 693113 692977 693066 693138 692993 693085 693069 693103 693200 693057 693065 693159 693127 693165 693101 693118 693000 693056 693085 693014 693082 693152 693186 693011 693075 693202 693049 693098 693046 693039...
result:
ok 200000 lines
Subtask #6:
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
Test #33:
score: 24
Accepted
time: 1178ms
memory: 104936kb
input:
5000 200 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1...
output:
5198000 5198000 5197999 5197998 5198000 5198000
result:
ok 6 lines
Test #34:
score: -24
Time Limit Exceeded
input:
5000 200 160 139 615 871 587 161 351 622 789 914 895 879 64 267 746 30 419 132 403 945 544 535 640 855 491 3 466 348 415 678 868 157 872 496 627 700 842 648 827 64 953 574 449 586 760 364 853 392 429 718 137 432 214 488 52 228 247 212 710 827 798 670 826 354 791 875 426 529 969 769 740 110 55 838 27...
output:
1566176 1570301 1568156 1567252 1565561 1567348 1564774 1567155 1564728 1567562 1567164 1565195 1566389 1565080 1561184 1565282 1570177 1568647 1565243 1567530 1568184 1565381 1564321 1563878 1567638 1565567 1569927 1564249 1568619 1570019 1563205 1565799 1564074 1566968 1561087 1559756 1563352 1567...