QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#559111 | #1154. Wombats | makrav# | 28 | 1190ms | 36164kb | C++20 | 3.2kb | 2024-09-11 20:16:54 | 2024-09-11 20:16:56 |
Judging History
answer
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
int dp[5000][200], HH[5000][200], VV[5000][200];
int RR, CC;
const int K = 50;
int fuck[100][200][200];
int ans[200][200];
void recalc_block(int ind) {
int row_start = ind * (K - 1), row_endd = min(RR - 1, (ind + 1) * (K - 1));
//cout << "rcbl " << ind << ' ' << row_start << ' ' << row_endd << '\n';
for (int JJ = 0; JJ < CC; JJ++) {
vector<vector<int>> dp(row_endd - row_start + 1, vector<int>(CC, 0));
for (int j1 = JJ - 1; j1 >= 0; j1--) {
dp.back()[j1] = dp.back()[j1 + 1] + HH[row_endd][j1];
}
for (int j1 = JJ + 1; j1 < CC; j1++) {
dp.back()[j1] = dp.back()[j1 - 1] + HH[row_endd][j1 - 1];
}
for (int i = row_endd - 1; i >= row_start; i--) {
for (int j = 0; j < CC; j++) {
dp[i - row_start][j] = dp[i - row_start + 1][j] + VV[i][j];
}
for (int j = 1; j < CC; j++) {
dp[i - row_start][j] = min(dp[i - row_start][j], dp[i - row_start][j - 1] + HH[i][j - 1]);
}
for (int j = CC - 2; j >= 0; j--) {
dp[i - row_start][j] = min(dp[i - row_start][j], dp[i - row_start][j + 1] + HH[i][j]);
}
}
//cout << JJ << ":\n";
for (int j = 0; j < CC; j++) fuck[ind][j][JJ] = dp[0][j];
// for (int j = 0; j < CC; j++) {
// cout<<ind << ' ' << j << ' ' << JJ << ' ' << fuck[ind][j][JJ] << '\n';
// }
// cout << '\n';
}
}
void calc_answers() {
int lb = -1;
for (int i = 0; i < 100; i++) {
if (i * (K - 1) >= RR - 1) break;
lb = i;
}
//cout << "calc " << lb << '\n';
for (int JE = 0; JE < CC; JE++) {
vector<int> curdp(CC);
for (int j = 0; j < CC; j++) curdp[j] = fuck[lb][j][JE];
vector<int> newdp(CC);
for (int i = lb - 1; i >= 0; i--) {
//cout << "yessir\n";
for (int j = 0; j < CC; j++) {
newdp[j] = 2e9 + 1;
for (int j2 = 0; j2 < CC; j2++) newdp[j] = min(newdp[j], curdp[j2] + fuck[i][j][j2]);
}
swap(newdp, curdp);
}
for (int j = 0; j < CC; j++) {
ans[j][JE] = curdp[j];
}
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
RR=R;
CC=C;
for(int i=0;i<5000;i++){
for (int j = 0; j < 200; j++) {
HH[i][j] = H[i][j];
VV[i][j] = V[i][j];
}
}
for (int i = 0; i < 100; i++) {
if (i * (K - 1) >= RR - 1) break;
recalc_block(i);
}
calc_answers();
}
void changeH(int P, int Q, int W) {
HH[P][Q] = W;
for (int i = 0; i < 100; i++) {
if (i * (K - 1) >= max(P + 1, RR - 1)) break;
if (i * (K - 1) <= P && P <= min(RR - 1, (i + 1) * (K - 1))) recalc_block(i);
}
calc_answers();
}
void changeV(int P, int Q, int W) {
VV[P][Q] = W;
for (int i = 0; i < 100; i++) {
if (i * (K - 1) >= RR - 1) break;
if (i * (K - 1) <= P && P <= min(RR - 1, (i + 1) * (K - 1))) recalc_block(i);
}
calc_answers();
}
int escape(int V1, int V2) {
return ans[V1][V2];
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 9
Accepted
time: 3ms
memory: 34220kb
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
Wrong Answer
time: 3ms
memory: 32416kb
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:
2454093 2454220 2454295 2454295 2454457 2455318 2455590 2456110 2455997 2455625 2455520 2455526 2455645 2455989 2456007 2455838 2455932 2455343 2455343 2455117 2455730 2455730 2455860 2455721 2455755 2455755 2455550 2455904 2455904 2456216 2456048 2456383 2456564 2456842 2456649 2456649 2456802 2457...
result:
wrong answer 1st lines differ - expected: '2499534', found: '2454093'
Subtask #2:
score: 12
Accepted
Test #9:
score: 12
Accepted
time: 0ms
memory: 14348kb
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: 12
Accepted
time: 2ms
memory: 14392kb
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: 12
Accepted
time: 2ms
memory: 14096kb
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: 12
Accepted
time: 0ms
memory: 18160kb
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: 12
Accepted
time: 3ms
memory: 16144kb
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: 12
Accepted
time: 3ms
memory: 16132kb
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: 12
Accepted
time: 3ms
memory: 16092kb
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: 12
Accepted
time: 36ms
memory: 16136kb
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: 12
Accepted
time: 4ms
memory: 16196kb
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: 186ms
memory: 16488kb
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: 16
Accepted
time: 179ms
memory: 18528kb
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: 16
Accepted
time: 236ms
memory: 16504kb
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: 16
Accepted
time: 241ms
memory: 18396kb
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: 16
Accepted
time: 236ms
memory: 16512kb
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: 16
Accepted
time: 1190ms
memory: 16504kb
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: 16
Accepted
time: 4ms
memory: 16096kb
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: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 0ms
memory: 36164kb
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:
2073084 2073343 2073137 2073282 2073080 2073339 2073282 2073137 2073339 2073080 2073132 2073277 2073132 2073277 2073382 2073237 2073237 2073382 2073237 2073382 2073500 2073241 2073164 2073309 2073164 2073309 2073164 2073309 2073107 2073366 2072985 2072840 2072840 2072985 2072985 2072840 2072783 2073...
result:
wrong answer 1st lines differ - expected: '2116460', found: '2073084'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%