QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#559115#1154. Wombatsmakrav#28 1247ms35936kbC++203.2kb2024-09-11 20:18:192024-09-11 20:18:19

Judging History

你现在查看的是最新测评结果

  • [2024-09-11 20:18:19]
  • 评测
  • 测评结果:28
  • 用时:1247ms
  • 内存:35936kb
  • [2024-09-11 20:18:19]
  • 提交

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 = 31;
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: 6ms
memory: 31256kb

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: 0ms
memory: 31300kb

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:

1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505183
1505...

result:

wrong answer 1st lines differ - expected: '2499534', found: '1505183'

Subtask #2:

score: 12
Accepted

Test #9:

score: 12
Accepted
time: 0ms
memory: 18184kb

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: 0ms
memory: 16124kb

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: 3ms
memory: 16136kb

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: 16124kb

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: 16112kb

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: 16136kb

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: 0ms
memory: 14124kb

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: 33ms
memory: 16212kb

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: 0ms
memory: 18208kb

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: 242ms
memory: 14520kb

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: 246ms
memory: 14544kb

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: 253ms
memory: 14536kb

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: 253ms
memory: 14612kb

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: 246ms
memory: 20800kb

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: 1247ms
memory: 16584kb

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: 3ms
memory: 14044kb

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: 4ms
memory: 35936kb

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:

1268116
1268374
1268173
1268317
1268116
1268374
1268317
1268173
1268374
1268116
1268173
1268317
1268173
1268317
1268317
1268173
1268173
1268317
1268173
1268317
1268374
1268116
1268173
1268317
1268173
1268317
1268173
1268317
1268116
1268374
1268317
1268173
1268173
1268317
1268317
1268173
1268116
1268...

result:

wrong answer 1st lines differ - expected: '2116460', found: '1268116'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%