QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#120617#1154. WombatsQwerty1232#76 9608ms241048kbC++173.8kb2023-07-07 01:23:132024-05-26 02:55:59

Judging History

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

  • [2024-05-26 02:55:59]
  • 评测
  • 测评结果:76
  • 用时:9608ms
  • 内存:241048kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 01:23:13]
  • 提交

answer

#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.L = b.L;
        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 > 0) {
            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: 6ms
memory: 10588kb

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: 9
Accepted
time: 6ms
memory: 10180kb

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: 9
Accepted
time: 38ms
memory: 11272kb

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: 9
Accepted
time: 9ms
memory: 10280kb

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: 9
Accepted
time: 9ms
memory: 10272kb

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: 9
Accepted
time: 1ms
memory: 4132kb

input:

2 1
0
1
3 0 0

output:

0

result:

ok single line: '0'

Test #7:

score: 9
Accepted
time: 0ms
memory: 3852kb

input:

2 1
1
1
3 0 0

output:

1

result:

ok single line: '1'

Test #8:

score: 9
Accepted
time: 0ms
memory: 3848kb

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

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: 1ms
memory: 5976kb

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: 1ms
memory: 6028kb

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: 1ms
memory: 5980kb

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: 1ms
memory: 5976kb

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: 1ms
memory: 6208kb

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: 1ms
memory: 6240kb

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

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: 1ms
memory: 6232kb

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: 629ms
memory: 11012kb

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: 642ms
memory: 10692kb

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: 645ms
memory: 10764kb

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: 665ms
memory: 10736kb

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: 637ms
memory: 10724kb

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: 2968ms
memory: 10768kb

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: 1ms
memory: 5892kb

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: 9ms
memory: 14664kb

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: 18
Accepted
time: 8ms
memory: 14740kb

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: 18
Accepted
time: 13ms
memory: 14668kb

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: 18
Accepted
time: 21ms
memory: 14760kb

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: 8893ms
memory: 241048kb

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: 21
Accepted
time: 8407ms
memory: 197940kb

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: 21
Accepted
time: 8891ms
memory: 198988kb

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: 21
Accepted
time: 9608ms
memory: 240948kb

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: 0
Time Limit Exceeded

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:

Unauthorized output

result: