QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#721875 | #6140. 矩阵游戏 | propane | 60 | 838ms | 6588kb | C++20 | 2.6kb | 2024-11-07 17:03:56 | 2024-11-07 17:03:57 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;
LL a[305][305];
vector<pair<int, int> > g[605];
LL d[605];
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n - 1; i++){
for(int j = 1; j <= m - 1; j++){
cin >> a[i][j];
}
}
for(int i = n - 1; i >= 1; i--){
for(int j = m - 1; j >= 1; j--){
a[i][j] -= a[i + 1][j] + a[i][j + 1] + a[i + 1][j + 1];
}
}
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= m; j++){
// cout << a[i][j] << " \n"[j == m];
// }
// }
for(int i = 1; i <= n + m; i++) g[i].clear();
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
// 0 <= row(i) - col(j) + a[i][j] <= 1000'000
if ((i + j) % 2 == 0){
g[j + n].push_back({i, 1000'00 - a[i][j]});
g[i].push_back({j + n, a[i][j]});
}
// 0 <= col(j) - row(i) + a[i][j] <= 1000'000
else{
g[i].push_back({j + n, 1000'00 - a[i][j]});
g[j + n].push_back({i, a[i][j]});
}
}
}
for(int i = 1; i <= n + m; i++){
g[0].push_back({i, 0});
}
memset(d, 0x3f, sizeof d);
d[0] = 0;
for(int _ = 0; _ < n + m; _++){
for(int i = 1; i <= n + m; i++){
for(auto [j, w] : g[i]){
d[j] = min(d[j], d[i] + w);
}
}
}
bool ok = true;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if ((i + j) % 2 == 0) a[i][j] += d[i];
else a[i][j] -= d[i];
if ((i + j) % 2 == 0) a[i][j] -= d[j + n];
else a[i][j] += d[j + n];
ok &= (a[i][j] >= 0) and (a[i][j] <= 1000'000);
}
}
if (ok){
cout << "YES" << '\n';
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cout << a[i][j] << " \n"[j == m];
}
}
}
else{
cout << "NO" << '\n';
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 3664kb
input:
10 3 3 9 21 22 16 3 3 28 30 13 4 3 3 17 10 5 30 3 3 30 27 30 25 3 3 22 19 28 12 3 3 30 27 21 28 3 3 4 25 11 5 3 3 12 24 24 30 3 3 5 4 27 8 3 3 20 29 17 18
output:
YES 0 5 0 0 4 12 18 0 0 YES 7 18 8 3 0 4 10 0 0 YES 17 0 0 0 0 10 5 0 20 YES 0 17 0 13 0 10 17 0 15 YES 0 9 0 13 0 10 15 0 2 YES 23 1 0 0 6 20 15 0 2 YES 0 4 16 0 0 5 11 0 0 YES 0 0 0 0 12 12 12 0 6 YES 0 0 0 5 0 4 22 0 4 YES 10 10 1 0 0 18 17 0 0
result:
ok you are right!!
Test #2:
score: 5
Accepted
time: 0ms
memory: 3716kb
input:
10 3 3 5 18 16 21 3 3 28 30 27 5 3 3 30 12 9 11 3 3 28 20 30 13 3 3 22 27 28 5 3 3 30 29 30 23 3 3 17 13 22 13 3 3 29 24 29 25 3 3 23 12 3 2 3 3 20 30 23 30
output:
YES 0 0 0 0 5 13 11 0 3 YES 0 17 8 11 0 5 16 0 0 YES 30 0 1 0 0 11 9 0 0 YES 1 6 1 19 2 11 9 0 0 YES 0 15 7 7 0 5 21 0 0 YES 21 0 6 0 9 14 21 0 0 YES 15 0 0 2 0 13 20 0 0 YES 20 0 0 0 9 15 20 0 1 YES 23 0 10 0 0 2 3 0 0 YES 0 0 0 0 20 10 3 0 0
result:
ok you are right!!
Test #3:
score: 5
Accepted
time: 0ms
memory: 3676kb
input:
10 3 3 17 22 17 27 3 3 30 24 30 30 3 3 11 16 10 15 3 3 29 18 19 27 3 3 12 2 25 26 3 3 27 28 29 30 3 3 14 11 8 16 3 3 29 27 26 15 3 3 1 21 25 12 3 3 30 28 21 27
output:
YES 0 0 0 0 17 5 0 0 5 YES 0 0 0 10 20 4 0 0 6 YES 0 7 0 0 4 5 6 0 6 YES 16 0 0 0 13 5 6 0 9 YES 0 0 0 10 2 0 13 0 24 YES 0 22 0 0 5 1 24 0 24 YES 11 3 0 0 0 8 8 0 8 YES 0 19 0 10 0 8 16 0 7 YES 0 1 8 0 0 12 25 0 0 YES 30 0 1 0 0 27 21 0 0
result:
ok you are right!!
Test #4:
score: 5
Accepted
time: 0ms
memory: 3604kb
input:
10 3 3 6 30 30 11 3 3 29 28 11 25 3 3 26 26 15 22 3 3 23 30 29 6 3 3 16 8 13 20 3 3 26 30 29 28 3 3 3 24 4 2 3 3 29 30 24 29 3 3 15 12 7 4 3 3 30 26 25 30
output:
YES 0 6 13 0 0 11 30 0 0 YES 29 0 3 0 0 25 11 0 0 YES 19 0 4 7 0 22 8 0 0 YES 0 4 20 19 0 6 10 0 0 YES 13 0 0 0 3 5 10 0 12 YES 0 14 0 1 11 5 17 0 12 YES 0 3 19 0 0 2 4 0 0 YES 9 0 1 0 20 9 4 0 0 YES 6 2 6 7 0 4 0 0 0 YES 5 0 0 0 25 1 0 0 4
result:
ok you are right!!
Test #5:
score: 5
Accepted
time: 0ms
memory: 3624kb
input:
10 10 2 240 8788 3257 6676 9748 4941 1268 2569 7827 10 2 9542 9328 8351 9362 9771 9183 8527 8640 7370 10 2 3144 7704 2054 9901 3567 120 2273 2407 4202 10 2 7337 9013 9119 9547 8526 8071 8475 6682 9273 10 2 746 9791 1891 3204 8908 1495 1353 9406 1176 10 2 9884 6039 4691 9956 8516 9454 9649 8966 9380 ...
output:
NO YES 1790 0 1620 6132 1576 0 6174 601 2587 0 3511 3673 1999 0 6528 0 2112 0 0 5258 NO YES 5469 0 0 1868 7145 0 0 1974 7573 0 953 0 7118 0 0 1357 5325 0 0 3948 NO YES 7096 0 0 2788 3251 0 0 1440 8516 0 0 0 9454 0 0 195 8771 0 0 609 NO YES 2263 0 6695 0 1746 0 223 7656 1191 0 5495 2359 54 0 7756 162...
result:
ok you are right!!
Test #6:
score: 5
Accepted
time: 1ms
memory: 3680kb
input:
10 10 2 7221 6762 7271 4154 1804 3226 6434 8357 2359 10 2 8581 5933 9174 9731 9716 9180 8744 9947 6264 10 2 282 9689 7228 960 2522 6806 7516 7002 9829 10 2 9202 8816 8250 9267 8287 8105 9707 8985 9226 10 2 2004 254 7197 7613 9790 5556 3064 6363 6489 10 2 7863 9827 9600 9998 7626 6038 9530 8772 8501 ...
output:
NO YES 7688 0 0 893 5040 0 0 4134 5597 0 1329 2790 5061 0 0 3683 6264 0 0 0 NO YES 4400 0 2341 2461 4014 0 4236 0 5031 0 1694 1562 4849 0 2586 2272 4127 0 0 5099 NO YES 1731 0 6132 0 3695 0 0 5905 4093 0 0 3533 2505 0 397 6628 1747 0 0 6754 NO YES 6291 0 453 1403 7172 0 0 0 9481 0 0 283 9133 0 0 711...
result:
ok you are right!!
Test #7:
score: 5
Accepted
time: 0ms
memory: 3680kb
input:
10 10 2 2492 6642 8650 4949 7971 7552 5729 6137 3224 10 2 8862 4232 4370 9422 9787 8443 9745 9230 9708 10 2 1073 3311 5736 6108 1985 2880 2596 1260 4678 10 2 9862 9822 8867 4686 9645 7259 7954 9855 9482 10 2 6532 3248 1799 3767 7693 4389 5786 1124 9586 10 2 7667 9393 6828 8642 9482 8512 8366 7067 87...
output:
YES 2492 0 0 0 6642 0 1714 294 2941 0 4736 294 2522 0 2913 294 2930 0 0 294 YES 8862 0 0 0 4232 0 0 138 9284 0 0 503 7940 0 0 1805 7425 0 0 2283 NO YES 8907 0 0 955 8867 0 0 0 4686 0 2812 2147 2300 0 3791 1863 4201 0 0 5281 NO YES 0 0 6218 1449 1726 0 5102 0 3540 0 2016 3926 2570 0 473 5323 1271 0 0...
result:
ok you are right!!
Test #8:
score: 0
Wrong Answer
time: 1ms
memory: 3932kb
input:
10 100 2 407406 741582 966880 693984 175204 991130 183615 326373 131306 366816 697972 180227 398068 835836 746523 999640 178807 545159 437329 536071 721606 306737 181599 455551 733444 231865 77996 588988 897019 804401 528918 524503 349494 623245 534144 344637 25518 791164 100668 547254 630911 346372...
output:
NO NO NO NO NO NO NO NO NO NO
result:
wrong answer expected: YES, found: NO
Test #9:
score: 0
Wrong Answer
time: 1ms
memory: 3868kb
input:
10 100 2 514849 121431 445450 996530 912655 547635 39581 89505 975458 843069 273144 700881 59053 289340 848708 32178 700710 194859 273472 213196 384827 341987 482545 308239 413944 599935 848280 843825 979288 195213 209986 440149 934390 768000 882462 200861 119570 174661 871708 511415 426500 576587 5...
output:
NO NO NO NO NO NO NO NO NO NO
result:
wrong answer expected: YES, found: NO
Test #10:
score: 0
Wrong Answer
time: 1ms
memory: 3944kb
input:
10 100 2 650385 567657 465159 181316 696069 211308 655715 128129 988551 838473 44280 61031 528962 277047 286263 142130 248066 307713 578918 695526 89569 48119 569157 673222 295474 923221 90394 912892 523136 369133 635906 272262 887296 438346 625250 217263 729637 256075 898161 999382 845113 626531 74...
output:
NO NO NO NO NO NO NO NO NO NO
result:
wrong answer expected: YES, found: NO
Test #11:
score: 5
Accepted
time: 837ms
memory: 6584kb
input:
10 300 298 0 0 1 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0...
output:
NO YES 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0...
result:
ok you are right!!
Test #12:
score: 5
Accepted
time: 803ms
memory: 6516kb
input:
10 297 296 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 0...
output:
NO YES 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0...
result:
ok you are right!!
Test #13:
score: 5
Accepted
time: 817ms
memory: 6504kb
input:
10 297 299 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 0 0 0 1 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1...
output:
NO YES 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0...
result:
ok you are right!!
Test #14:
score: 5
Accepted
time: 824ms
memory: 6564kb
input:
10 298 299 0 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0...
output:
NO YES 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0...
result:
ok you are right!!
Test #15:
score: 5
Accepted
time: 822ms
memory: 6536kb
input:
10 298 296 0 1 1 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 1...
output:
NO YES 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0...
result:
ok you are right!!
Test #16:
score: 0
Wrong Answer
time: 821ms
memory: 6588kb
input:
10 295 299 3600561 469227 1519243 508870 2714139 2548515 3416122 1633507 1829918 1551817 3098121 1670950 2106466 1946727 1581396 3426393 1988045 2888135 2146489 1534631 2721599 3729764 456043 293501 882439 3099151 2941143 3610816 549774 1066237 3189705 2413286 2316602 3976215 3845403 862960 241887 2...
output:
NO NO NO NO NO NO NO NO NO NO
result:
wrong answer expected: YES, found: NO
Test #17:
score: 0
Wrong Answer
time: 838ms
memory: 6572kb
input:
10 298 297 1203979 2459461 1123626 2165742 593951 2361185 60882 1597698 966249 1407808 2665213 1585110 1730464 732707 2642476 54357 96750 3459440 500455 1509802 2084769 1885656 824649 1394960 3065480 1964072 626742 582644 617926 652074 1646286 250370 1154127 1955950 327344 753408 2005921 2832519 933...
output:
NO NO NO NO NO NO NO NO NO NO
result:
wrong answer expected: YES, found: NO
Test #18:
score: 0
Wrong Answer
time: 817ms
memory: 6560kb
input:
10 296 296 2917992 3146628 3606537 755096 2325656 3902232 2435726 2851482 3134088 1183312 3680091 2970485 3974463 2456731 3306154 400789 1137399 1266637 1849976 2126197 1039996 2867787 711979 2828033 1651264 3781772 1152035 2861694 2479767 1853717 886722 2972156 4583 903432 3364054 3947134 3871761 3...
output:
NO NO NO NO NO NO NO NO NO NO
result:
wrong answer expected: YES, found: NO
Test #19:
score: 0
Wrong Answer
time: 821ms
memory: 6528kb
input:
10 297 297 13391 712464 2974864 1439202 1447544 1413180 800048 597109 3349875 2034207 1467293 796338 2354278 171222 1066675 2532591 208592 123178 2912280 3309432 3409173 1029236 2315777 2135394 3355241 69077 3113692 2937527 2948148 1151724 1640840 870814 42569 2304251 726055 3017332 2049772 2646010 ...
output:
NO NO NO NO NO NO NO NO NO NO
result:
wrong answer expected: YES, found: NO
Test #20:
score: 0
Wrong Answer
time: 827ms
memory: 6556kb
input:
10 297 295 2251173 2102586 854138 210476 3746962 1050335 357886 1246625 2048656 3914401 2622120 2500826 3210040 3638713 646704 3538951 2675262 2202513 1600647 2451535 120429 782584 3574033 3344068 580591 2179489 3256587 684504 1805546 599720 3155847 2286982 2960267 502472 3365334 1420188 2393737 228...
output:
NO NO NO NO NO NO NO NO NO NO
result:
wrong answer expected: YES, found: NO