QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#721884 | #6140. 矩阵游戏 | propane | 100 ✓ | 836ms | 6624kb | C++20 | 2.6kb | 2024-11-07 17:04:54 | 2024-11-07 17:04:55 |
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'000 - 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'000 - 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: 3720kb
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: 3652kb
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: 3632kb
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: 3720kb
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: 3736kb
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: 0ms
memory: 3660kb
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: 3608kb
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: 5
Accepted
time: 0ms
memory: 3916kb
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 YES 529624 0 0 220505 629842 0 0 252235 664289 0 0 330072 648474 0 0 301947 542206 0 0 133865 475779 0 0 117659 304071 0 0 382739 159037 0 0 783998 200904 0 0 576098 78459 0 0 784018 121346 0 0 475587 348606 0 0 568815 13833 0 0 979137 19943 0 0 575697 344429 0 0 517323 134004 0 0 824372 39263 0 ...
result:
ok you are right!!
Test #9:
score: 5
Accepted
time: 1ms
memory: 3896kb
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 YES 615952 0 0 377584 418860 0 0 579713 282384 0 0 512911 400157 0 251485 325800 158607 0 0 841392 90635 0 200498 641828 102411 0 802263 0 104644 0 261349 559368 76607 0 0 919406 30968 0 0 821646 164428 0 0 578213 359654 0 0 323782 561344 0 0 314046 269602 0 0 729148 0 0 0 615762 346631 0 0 64928...
result:
ok you are right!!
Test #10:
score: 5
Accepted
time: 1ms
memory: 3884kb
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 YES 864373 0 0 133199 698114 0 0 273481 709285 0 0 263356 348526 0 0 293622 676715 0 0 259457 180751 0 0 360307 587951 0 0 331511 496359 0 0 456555 186235 0 0 768865 200054 0 0 336105 0 0 0 740775 96579 0 0 861726 69309 0 0 590322 266038 0 0 470999 180716 0 0 667541 73026 0 0 797699 40641 0 0 750...
result:
ok you are right!!
Test #11:
score: 5
Accepted
time: 817ms
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: 800ms
memory: 6568kb
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: 808ms
memory: 6624kb
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: 810ms
memory: 6624kb
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: 809ms
memory: 6564kb
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: 5
Accepted
time: 807ms
memory: 6500kb
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 YES 59099 344576 921318 360736 206362 284343 734692 754085 986376 514336 84113 428243 308746 270361 32824 293696 688715 574274 666917 169509 782311 314903 828913 965079 721458 556275 341930 324941 463657 9155 70794 811214 681150 216907 891535 892729 695532 254029 576424 211203 677024 441576 88618...
result:
ok you are right!!
Test #17:
score: 5
Accepted
time: 836ms
memory: 6624kb
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 YES 491504 948332 190170 68498 381314 580879 429750 586869 529205 281553 141694 585581 569378 52931 705539 656570 980313 748770 326212 298179 311326 661669 207034 443055 210326 457204 234550 50170 515500 408484 857033 358082 828484 771546 793040 272384 22973 782182 140709 507210 725588 990177 221...
result:
ok you are right!!
Test #18:
score: 5
Accepted
time: 824ms
memory: 6564kb
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 YES 914892 344276 529645 237463 6516 852692 565281 118658 506203 706015 692487 711441 525529 419090 212185 413399 132459 374375 280999 371083 712751 545647 104037 344044 926273 787916 404550 106139 533010 223238 299405 585002 169721 2415 514071 96645 863409 186862 906290 197963 838226 954477 8899...
result:
ok you are right!!
Test #19:
score: 5
Accepted
time: 830ms
memory: 6516kb
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 YES 343403 178082 498742 783468 800734 811687 781642 0 809989 842954 94987 716269 202784 696338 262019 178928 965671 946168 305685 59435 888824 269454 514238 85583 643027 328565 37159 433074 887909 327931 953870 315214 345186 712426 16531 444456 549764 339156 121243 648632 812182 793964 524618 16...
result:
ok you are right!!
Test #20:
score: 5
Accepted
time: 804ms
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 YES 303432 856959 369315 604769 149956 837278 955015 9506 514373 972657 910151 579460 569410 813715 341016 241736 469702 780838 464616 109740 818326 596622 140917 997695 717555 1000000 786862 369816 381730 780883 630631 642473 457872 561078 260290 20702 594972 133269 373649 365015 333296 708363 2...
result:
ok you are right!!
Extra Test:
score: 0
Extra Test Passed