QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #137385 | #4576. Job Lookup | liwuyou | AC ✓ | 20ms | 4760kb | C++14 | 1.4kb | 2023-08-10 11:48:04 | 2023-08-10 11:48:07 |
Judging History
answer
#include <iostream>
using namespace std;
const int N = 205;
long long dp[N][N], p[N][N], sum[N][N];
int a[N][N], ans[N];
void dfs(int l, int r, int f) {
if(l > r) {
return;
}
ans[p[l][r]] = f;
dfs(l, p[l][r] - 1, p[l][r]);
dfs(p[l][r] + 1, r, p[l][r]);
}
long long f(int x1, int y1, int x2, int y2) {
if (x1 > x2 || y1 > y2) {
return 0;
}
return sum[x1 - 1][y1 - 1] + sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1];
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
dp[i][j] = 1145141919810114514;
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> a[i][j];
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
}
for(int i = 1; i <= n; i++) {
p[i][i] = i;
dp[i][i] = dp[i][i - 1] = 0;
}
dp[n + 1][n] = 0;
for(int l = 2; l <= n; l++) {
for(int i = 1, j = l; j <= n; i++, j++) {
for(int k = i; k <= j; k++) {
long long cnt = dp[i][k - 1] + dp[k + 1][j];
cnt += f(i, 1, k - 1, i - 1) + f(i, k, k - 1, n) + f(k + 1, 1, j, k) + f(k + 1, j + 1, j, n);
if(dp[i][j] > cnt) {
dp[i][j] = cnt;
p[i][j] = k;
}
}
}
}
int mid = p[1][n];
dfs(1, mid - 1, mid);
dfs(mid + 1, n, mid);
for(int i = 1; i <= n; i++) {
cout << ans[i] << ' ';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3492kb
input:
4 0 566 1 0 566 0 239 30 1 239 0 1 0 30 1 0
output:
2 4 2 0
result:
ok Cost = 839
Test #2:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
1 0
output:
0
result:
ok Cost = 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 0 332748503 68411722 332748503 0 397254748 68411722 397254748 0
output:
0 1 2
result:
ok Cost = 866826695
Test #4:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
4 0 332748503 68411722 573050229 332748503 0 397254748 908840922 68411722 397254748 0 353868720 573050229 908840922 353868720 0
output:
0 4 2 1
result:
ok Cost = 3457615511
Test #5:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
10 0 932748491 968411713 973050224 951408235 908975816 965336241 921466600 977999663 912576018 932748491 0 997254745 908840904 905218369 973072462 916872934 965253666 918625182 943911377 968411713 997254745 0 953868708 980276348 935238286 919123461 986073987 916765289 961600980 973050224 908840904 9...
output:
0 3 1 5 7 5 3 9 7 9
result:
ok Cost = 111058701527
Test #6:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
10 0 332748503 68411722 573050229 51408244 508975830 465336245 321466612 977999672 412576022 332748503 0 397254748 908840922 605218384 73072471 616872949 265253668 418625195 143911387 68411722 397254748 0 353868720 980276357 935238295 819123478 586073992 616765304 61600980 573050229 908840922 353868...
output:
0 3 4 7 4 5 9 7 1 9
result:
ok Cost = 55083155252
Test #7:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
40 0 332748503 68411722 573050229 51408244 508975830 465336245 321466612 977999672 412576022 352305625 443204518 508003778 82048141 39334271 80084611 462704915 914540254 646160102 4656254 547231132 908263820 491052373 208533451 581133919 718353902 247698641 565573401 572818944 522543559 956776164 12...
output:
0 3 4 6 4 10 8 6 8 35 12 14 12 18 16 14 16 26 20 22 20 18 24 22 24 10 29 27 31 29 26 33 31 33 39 37 35 37 1 39
result:
ok Cost = 2028905649805
Test #8:
score: 0
Accepted
time: 5ms
memory: 4024kb
input:
100 0 332748503 68411722 573050229 51408244 508975830 465336245 321466612 977999672 412576022 352305625 443204518 508003778 82048141 39334271 80084611 462704915 914540254 646160102 4656254 547231132 908263820 491052373 208533451 581133919 718353902 247698641 565573401 572818944 522543559 956776164 1...
output:
2 100 4 6 4 2 8 10 8 14 12 10 12 22 16 18 16 14 20 18 20 92 24 26 24 30 28 26 28 38 32 34 32 30 36 34 36 54 40 42 40 46 44 42 44 38 48 50 48 46 52 50 52 22 57 55 59 57 64 61 62 59 62 73 66 69 68 66 64 71 69 71 54 75 77 75 82 80 78 77 80 73 84 87 84 85 82 89 87 91 89 6 94 96 94 92 98 96 98 0
result:
ok Cost = 18172468690391
Test #9:
score: 0
Accepted
time: 10ms
memory: 4308kb
input:
150 0 332748503 68411722 573050229 51408244 508975830 465336245 321466612 977999672 412576022 352305625 443204518 508003778 82048141 39334271 80084611 462704915 914540254 646160102 4656254 547231132 908263820 491052373 208533451 581133919 718353902 247698641 565573401 572818944 522543559 956776164 1...
output:
2 150 4 6 4 10 8 6 8 146 12 14 12 18 16 14 16 26 20 22 20 18 24 22 24 42 28 30 28 34 32 30 32 26 36 38 36 34 40 38 40 73 44 46 44 50 48 46 48 58 52 54 52 50 56 54 56 42 60 62 60 66 64 62 64 58 69 67 66 71 69 71 130 75 77 75 81 79 77 79 89 83 85 83 81 87 85 87 102 91 92 96 94 92 94 89 99 97 96 99 100...
result:
ok Cost = 46946371577923
Test #10:
score: 0
Accepted
time: 19ms
memory: 4484kb
input:
200 0 332748503 68411722 573050229 51408244 508975830 465336245 321466612 977999672 412576022 352305625 443204518 508003778 82048141 39334271 80084611 462704915 914540254 646160102 4656254 547231132 908263820 491052373 208533451 581133919 718353902 247698641 565573401 572818944 522543559 956776164 1...
output:
0 3 5 3 9 7 5 7 195 11 13 11 17 15 13 15 25 19 21 19 17 23 21 23 41 27 29 27 33 31 29 31 25 35 37 35 33 39 37 39 74 43 44 46 44 50 48 46 48 58 52 54 52 50 56 54 56 41 60 62 60 66 64 62 64 58 68 70 68 66 72 70 72 145 76 78 76 82 80 78 80 92 84 86 84 82 89 87 86 91 89 109 94 96 94 100 98 96 98 92 102 ...
result:
ok Cost = 91157821109054
Test #11:
score: 0
Accepted
time: 20ms
memory: 4656kb
input:
200 0 532748503 268411722 673050229 805218384 273072471 816872949 686073992 785841791 436077288 149911163 838685583 929355802 143131025 114630323 659487536 684376179 746160102 998357488 747231132 966105995 772651731 385183637 145898819 967812355 919014579 282566326 993935928 951862063 315235362 9867...
output:
2 200 4 6 4 10 8 6 8 18 12 14 12 10 16 14 16 188 20 22 20 26 24 22 24 35 29 27 31 29 26 33 31 33 51 37 39 37 43 41 39 41 35 45 47 45 43 49 47 49 18 53 55 53 60 57 55 57 58 68 62 64 62 60 66 64 66 84 70 72 70 76 74 72 74 68 78 80 78 76 82 80 82 123 86 88 86 92 90 88 90 100 94 96 94 92 98 96 98 84 102...
result:
ok Cost = 99939956086082
Test #12:
score: 0
Accepted
time: 19ms
memory: 4704kb
input:
200 0 832748502 568411721 573050228 551408243 508975828 965336245 821466611 977999671 912576022 852305625 943204517 508003777 582048140 539334271 580084611 962704914 914540253 646160101 504656254 547231130 908263819 991052373 708533450 581133918 718353901 747698641 565573399 572818942 522543558 9567...
output:
0 3 5 3 9 7 5 7 195 11 13 11 18 16 14 13 16 34 20 22 20 26 24 22 24 18 28 30 28 26 32 30 32 51 36 38 36 42 40 38 40 34 44 46 44 42 49 47 46 49 83 53 55 53 59 57 55 57 67 61 63 61 59 65 63 65 51 69 71 69 75 73 71 73 67 77 79 77 75 81 79 81 147 85 87 85 91 89 87 89 99 93 95 93 91 97 95 97 115 101 103 ...
result:
ok Cost = 136322555645526
Test #13:
score: 0
Accepted
time: 13ms
memory: 4544kb
input:
200 0 932748491 968411713 973050224 951408235 908975816 965336241 921466600 977999663 912576018 952305622 984760490 960273802 949338660 997669676 938783350 908531617 975192826 960856776 978080590 976095738 977232492 905504686 919030911 935259571 975232486 933215764 931013147 931359037 921628466 9080...
output:
0 3 5 3 9 7 5 7 195 11 13 11 17 15 13 15 25 19 21 19 17 23 21 23 9 27 29 27 33 31 29 31 41 35 37 35 33 39 37 39 57 43 45 43 49 47 45 47 41 51 53 51 49 55 53 55 25 59 61 59 65 63 61 63 73 67 69 67 65 71 69 71 89 75 77 75 81 79 77 79 73 83 85 83 81 87 85 87 121 91 93 91 97 95 93 95 105 99 101 99 97 10...
result:
ok Cost = 172562888575976
Test #14:
score: 0
Accepted
time: 19ms
memory: 4536kb
input:
200 0 992748371 998411617 993050172 991408140 998975681 999889219 999587523 998171756 990795343 990790402 999925180 999325463 999355720 996012019 994897975 994428683 991265956 999313356 992588102 997251892 993985604 992578763 991596542 994017662 997977226 992808134 990425822 998015009 992651105 9982...
output:
0 3 1 5 7 5 11 9 7 9 19 13 15 13 11 17 15 17 35 21 23 21 27 25 23 25 19 29 31 29 27 33 31 33 173 37 39 37 43 41 39 41 51 45 47 45 43 49 47 49 67 53 55 53 59 57 55 57 51 61 63 61 59 65 63 65 99 69 71 69 75 73 71 73 83 77 79 77 75 81 79 81 67 85 87 85 91 89 87 89 83 93 95 93 91 97 95 97 35 101 103 101...
result:
ok Cost = 180781225045465
Test #15:
score: 0
Accepted
time: 20ms
memory: 4756kb
input:
200 0 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 10000000...
output:
0 3 1 5 3 7 9 7 5 11 13 11 17 15 13 15 25 19 21 19 17 23 21 23 9 27 29 27 33 31 29 31 41 35 37 35 33 39 37 39 25 43 45 43 49 47 45 47 57 51 53 51 49 55 53 55 73 59 61 59 65 63 61 63 57 67 69 67 65 71 69 71 41 75 77 75 81 79 77 79 89 83 85 83 81 87 85 87 105 91 93 91 97 95 93 95 89 99 101 99 97 103 1...
result:
ok Cost = 181689000000000
Test #16:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
30 0 667251498 68411721 73050228 51408243 991024172 465336245 321466611 477999671 412576022 352305625 443204517 8003777 82048140 39334271 80084611 462704914 414540253 146160101 4656254 47231130 408263819 491052373 208533450 81133918 218353901 247698641 65573399 72818942 22543558 667251498 0 39725474...
output:
2 30 4 6 4 2 8 11 10 8 16 13 11 15 13 6 18 20 18 24 22 20 22 16 26 24 28 26 28 0
result:
ok Cost = 512429322042
Test #17:
score: 0
Accepted
time: 19ms
memory: 4760kb
input:
200 0 667251498 68411721 73050228 51408243 8975828 465336245 321466611 477999671 412576022 352305625 443204517 8003777 82048140 39334271 80084611 462704914 414540253 146160101 4656254 47231130 408263819 491052373 208533450 81133918 218353901 247698641 65573399 72818942 22543558 456776162 122486033 5...
output:
2 4 2 8 6 4 6 16 10 12 10 8 14 12 14 186 18 20 18 24 22 20 22 34 26 28 26 24 30 31 28 33 31 51 36 38 36 42 40 38 40 34 44 46 44 42 49 47 46 49 83 53 55 53 59 57 55 57 67 61 63 61 59 65 63 65 51 69 71 69 75 73 71 73 67 77 79 77 75 81 79 81 151 85 87 85 91 89 87 89 100 93 96 93 94 91 98 96 98 119 102 ...
result:
ok Cost = 45769837137749
Test #18:
score: 0
Accepted
time: 18ms
memory: 4544kb
input:
200 0 967251509 68411713 73050224 51408235 8975816 65336241 21466600 77999663 12576018 52305622 84760490 60273802 49338660 97669676 38783350 8531617 75192826 60856776 78080590 76095738 77232492 5504686 19030911 35259571 75232486 33215764 31013147 31359037 21628466 8013085 7619133 84143639 94396899 8...
output:
2 4 2 8 6 4 6 16 10 12 10 8 14 12 14 32 18 20 18 24 22 20 22 16 26 28 26 24 30 28 30 63 34 36 34 41 38 36 38 39 49 43 45 43 41 47 45 47 32 51 52 55 54 52 49 57 59 57 55 61 59 61 142 65 67 65 73 69 70 67 72 70 85 75 78 75 76 73 80 82 80 78 82 83 104 87 91 89 87 89 96 93 91 93 94 85 98 100 98 96 102 1...
result:
ok Cost = 9470288704876
Test #19:
score: 0
Accepted
time: 16ms
memory: 4608kb
input:
200 0 567251497 831588278 573050229 705218384 173072471 716872949 586073992 685841791 336077288 49911163 738685583 829355802 43131025 14630323 559487536 584376179 646160102 898357488 647231132 866105995 672651731 285183637 45898819 867812355 819014579 182566326 893935928 851862063 215235362 88672521...
output:
2 200 4 6 4 10 8 6 8 18 12 14 12 10 16 14 16 188 20 22 20 26 24 22 24 35 29 27 31 29 26 33 31 33 51 37 39 37 43 41 39 41 35 45 47 45 43 49 47 49 18 53 55 53 60 57 55 57 58 68 62 64 62 60 66 64 66 84 70 72 70 76 74 72 74 68 78 80 78 76 82 80 82 123 86 88 86 92 90 88 90 100 94 96 94 92 98 96 98 84 102...
result:
ok Cost = 81819250229946
Test #20:
score: 0
Accepted
time: 14ms
memory: 4704kb
input:
200 0 967251509 931588287 73050224 51408235 8975816 65336241 21466600 77999663 12576018 52305622 84760490 60273802 49338660 97669676 38783350 8531617 75192826 60856776 78080590 76095738 77232492 5504686 19030911 35259571 75232486 33215764 31013147 31359037 21628466 8013085 7619133 84143639 94396899 ...
output:
0 3 1 5 7 5 3 10 8 14 12 10 12 7 16 18 16 22 20 18 20 29 24 26 24 22 26 27 14 31 33 31 38 35 33 35 36 43 40 38 40 41 58 45 47 45 51 49 47 49 43 53 55 53 51 55 56 29 60 63 60 61 69 66 64 63 66 67 80 72 70 75 74 72 69 77 75 77 78 103 83 81 86 83 84 92 89 87 86 89 90 80 94 96 94 92 98 100 98 96 100 101...
result:
ok Cost = 9436459999910
Test #21:
score: 0
Accepted
time: 19ms
memory: 4608kb
input:
200 0 132748498 931588282 173050227 51408240 108975824 65336243 121466607 177999668 12576020 152305624 43204512 891996224 82048137 39334271 80084611 62704909 114540250 46160099 4656254 147231126 108263816 91052371 8533446 181133917 118353899 47698640 165573395 172818938 122543557 156776156 122486030...
output:
0 3 5 3 199 7 9 7 13 11 9 11 5 15 17 15 21 19 17 19 30 23 25 23 21 27 25 29 27 46 32 34 32 38 36 34 36 30 40 42 40 38 44 42 44 77 48 50 48 53 50 51 61 55 57 55 53 59 57 59 46 63 65 63 69 67 65 67 61 71 73 71 69 75 73 75 150 79 81 79 84 81 82 88 86 84 86 96 90 92 90 88 94 92 94 112 98 100 98 104 102 ...
result:
ok Cost = 18479150925676
Test #22:
score: 0
Accepted
time: 14ms
memory: 4588kb
input:
200 0 867251500 168411720 273050228 151408242 8975826 165336244 121466609 77999669 112576021 52305624 284760494 60273814 149338665 197669683 138783353 8531629 175192831 260856780 278080594 76095748 177232505 205504688 219030917 35259583 75232486 233215774 231013155 231359045 221628480 8013087 761914...
output:
2 4 2 8 6 4 6 193 10 12 10 16 14 12 14 24 18 20 18 16 22 20 22 41 26 27 29 27 33 31 29 31 24 35 37 35 33 39 37 39 76 43 45 43 49 47 45 47 58 51 53 51 49 55 53 55 56 41 60 62 60 66 64 62 64 58 68 70 68 66 73 71 70 73 74 142 78 80 78 84 82 80 82 92 86 88 86 84 90 88 90 109 94 96 94 101 98 99 96 99 92 ...
result:
ok Cost = 27400943998238
Test #23:
score: 0
Accepted
time: 15ms
memory: 4592kb
input:
200 0 867251499 268411721 173050228 251408243 308975828 65336244 121466610 177999670 12576021 352305625 243204516 108003777 282048140 39334271 80084611 262704913 114540252 246160101 4656254 347231130 108263818 91052372 8533449 181133918 318353901 247698641 365573399 372818942 122543558 356776161 322...
output:
2 200 4 6 4 10 8 6 8 196 12 14 12 18 16 14 16 26 20 22 20 18 24 22 24 10 28 30 28 34 32 30 32 42 36 38 36 34 40 38 40 58 44 46 44 50 48 46 48 42 52 54 52 50 56 54 56 26 60 62 60 67 64 62 64 65 78 69 71 69 67 73 75 73 71 77 75 94 80 82 80 86 84 82 84 78 88 90 88 86 92 90 92 127 96 99 96 97 103 101 99...
result:
ok Cost = 36634563214407
Test #24:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
31 0 33333333 66666666 100000000 133333333 166666666 200000000 233333333 266666666 300000000 333333333 366666666 400000000 433333333 466666666 500000000 533333333 566666666 600000000 633333333 666666666 700000000 733333333 766666666 800000000 833333333 866666666 900000000 933333333 966666666 1000000...
output:
0 3 5 3 30 7 9 7 13 11 9 11 22 15 18 17 15 13 20 18 20 5 24 26 24 22 28 26 28 1 30
result:
ok Cost = 836233332607
Test #25:
score: 0
Accepted
time: 11ms
memory: 4592kb
input:
200 0 5025125 10050251 15075376 20100502 25125628 30150753 35175879 40201005 45226130 50251256 55276381 60301507 65326633 70351758 75376884 80402010 85427135 90452261 95477386 100502512 105527638 110552763 115577889 120603015 125628140 130653266 135678391 140703517 145728643 150753768 155778894 1608...
output:
0 3 5 3 199 7 9 7 13 11 9 11 21 15 17 15 13 19 17 19 191 23 25 23 29 27 25 27 37 31 33 31 29 35 33 35 63 39 41 39 47 43 41 45 43 45 37 49 51 49 55 53 51 53 47 57 59 57 55 61 59 61 159 65 67 65 71 69 67 69 79 73 75 73 71 77 75 77 95 81 83 81 87 85 83 85 79 89 91 89 87 93 91 93 127 97 99 97 103 101 99...
result:
ok Cost = 65393547647622
Test #26:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
31 0 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1000000000 0 1000000000 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1000000000 0 0 0 1000000000 0 1000000000 0 0 0 0 0 0 0 0 0 0 0 0...
output:
2 4 2 8 6 4 6 16 10 12 10 8 14 12 14 0 18 20 18 24 22 20 22 16 26 28 26 24 30 28 30
result:
ok Cost = 30000000000
Test #27:
score: 0
Accepted
time: 12ms
memory: 4704kb
input:
200 0 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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:
2 4 2 7 6 4 13 9 10 7 12 10 26 15 17 15 20 19 17 13 22 23 20 25 23 51 28 30 28 33 32 30 39 35 36 33 38 36 26 41 42 45 44 42 39 47 48 45 50 48 101 53 55 53 58 57 55 64 60 61 58 63 61 76 66 67 70 69 67 64 72 73 70 75 73 51 78 80 78 83 82 80 89 85 86 83 88 86 76 91 92 95 94 92 89 97 98 95 100 98 0 103 ...
result:
ok Cost = 199000000000
Test #28:
score: 0
Accepted
time: 10ms
memory: 4540kb
input:
200 0 967251509 68411713 73050224 51408235 8975816 65336241 21466600 77999663 12576018 52305622 84760490 60273802 49338660 97669676 38783350 8531617 75192826 60856776 78080590 76095738 77232492 5504686 19030911 35259571 75232486 33215764 31013147 31359037 21628466 8013085 7619133 84143639 94396899 8...
output:
2 4 2 7 6 4 13 9 10 7 12 10 26 15 17 15 20 19 17 13 22 23 20 25 23 51 28 30 28 33 32 30 39 35 36 33 38 36 26 41 42 45 44 42 39 47 48 45 50 48 101 53 55 53 58 57 55 64 60 61 58 63 61 76 66 67 70 69 67 64 72 73 70 75 73 51 78 80 78 83 82 80 89 85 86 83 88 86 76 91 92 95 94 92 89 97 98 95 100 98 151 10...
result:
ok Cost = 9366708033493