QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #707908 | #7051. Largest Common Submatrix | Loxilante | WA | 138ms | 73228kb | C++20 | 2.9kb | 2024-11-03 18:05:59 | 2024-11-04 16:55:25 |
Judging History
answer
#define F_C
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i < r; i++)
#define hrp(i, l, r) for(int i = l; i <= r; i++)
#define rev(i, r, l) for(int i = r; i >= l; i--)
#define int ll
using namespace std;
typedef long long ll;
template<typename tn = int> tn next(void) { tn k; cin>>k; return k; }
#ifndef LOCAL
#define D(...) 0
#endif
const int U = 1.5e3;
int w[U][U], l[U][U], r[U][U], u[U][U], t[U*U];
bool sl[U][U], su[U][U];
signed main(void)
{
#ifdef LOCAL
// freopen("C:\\Users\\Loxil\\Desktop\\IN.txt", "r", stdin);
// freopen("C:\\Users\\Loxil\\Desktop\\OUT.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin>>n>>m;
rep(i, 0, n) rep(j, 0, m) t[next()] = i*m+j+1;
rep(i, 0, n) rep(j, 0, m) w[i][j] = t[next()], l[i][j] = r[i][j] = j, u[i][j] = 1;
int col = 0;
rep(i, 0, n) rep(j, 0, m)
{
if (i && w[i][j] == w[i-1][j]+m) su[i][j] = 1;
if (j && w[i][j] == w[i][j-1]+1) sl[i][j] = 1;
}
rep(i, 0, n) rep(j, 1, m) if (su[i][j-1]) l[i][j] = l[i][j-1];
rep(i, 0, n) rev(j, m-2, 0) if (sl[i][j+1]) r[i][j] = r[i][j+1];
int ans = 0;
rep(i, 0, n) rep(j, 0, m)
{
if (i && su[i][j])
{
l[i][j] = max(l[i][j], l[i-1][j]);
r[i][j] = min(r[i][j], r[i-1][j]);
u[i][j] = u[i-1][j]+1;
}
ans = max(ans, (r[i][j]-l[i][j]+1)*u[i][j]);
}
cout<<ans<<endl;
return 0;
}
/*
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 2 13 11
5 6 7 8
3 10 4 12
9 14 15 16
12 12
144 73 133 126 22 86 83 13 120 62 101 39
26 7 141 125 3 40 99 140 114 28 68 27
42 17 85 35 71 50 46 45 5 14 47 2
49 9 88 32 18 97 29 95 8 109 1 76
111 48 60 132 20 115 138 43 135 112 4 92
55 143 127 52 117 36 84 107 110 15 105 104
74 37 102 129 108 23 98 38 19 122 6 59
33 90 118 89 116 11 56 134 100 81 66 12
31 82 130 75 128 63 77 103 94 65 16 34
106 30 53 80 54 51 93 58 79 91 121 123
61 139 96 64 119 10 137 24 67 78 44 25
72 131 113 57 70 69 124 41 87 136 21 142
144 28 1 51 127 80 74 79 141 24 21 34
116 136 62 123 3 40 70 109 8 111 4 105
76 11 85 35 71 50 46 45 37 139 49 94
125 124 108 32 18 97 29 95 10 142 81 130
5 66 60 132 20 115 138 83 61 30 91 47
99 100 121 52 117 36 84 140 122 103 75 64
82 89 104 129 16 78 13 128 65 53 6 107
48 110 58 12 38 33 90 43 17 77 63 96
118 39 88 134 143 126 55 137 31 9 44 135
102 67 42 114 72 73 54 133 106 26 112 56
25 68 119 22 93 86 57 7 120 92 113 23
27 59 41 101 131 14 15 98 87 2 69 19
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15868kb
input:
3 4 5 6 7 8 1 2 3 4 9 10 11 12 5 6 8 7 1 2 4 3 12 11 10 9
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 2ms
memory: 15964kb
input:
10 10 13 2 57 50 1 28 37 87 30 46 66 47 33 69 83 52 97 55 91 18 9 48 23 35 98 8 7 95 90 5 3 53 43 36 96 59 26 4 70 17 71 100 15 94 25 72 84 89 21 73 64 34 22 29 42 92 85 78 86 62 99 79 67 11 6 19 24 51 77 74 75 16 88 44 93 39 41 82 56 65 12 40 63 54 10 60 32 45 20 80 49 61 76 14 81 68 27 31 58 38 13...
output:
100
result:
ok 1 number(s): "100"
Test #3:
score: 0
Accepted
time: 0ms
memory: 15964kb
input:
10 10 6 48 98 83 7 56 22 49 61 34 8 87 91 100 16 17 86 24 9 23 94 50 81 59 51 21 52 20 33 25 73 1 70 45 36 31 88 90 12 69 64 57 60 5 85 29 37 96 92 41 89 67 79 84 35 68 46 18 38 63 27 55 65 95 11 43 47 72 80 66 75 39 58 62 77 53 15 40 3 71 32 82 10 99 44 2 30 76 74 28 19 78 13 97 26 42 54 14 4 93 6 ...
output:
80
result:
ok 1 number(s): "80"
Test #4:
score: 0
Accepted
time: 2ms
memory: 15920kb
input:
10 10 37 16 29 24 14 20 41 63 4 15 71 99 17 26 33 47 83 55 89 52 32 22 95 44 81 93 78 31 42 12 94 70 25 46 18 97 57 62 68 67 21 69 54 27 13 96 64 48 59 28 11 49 9 73 100 90 85 36 2 58 74 53 98 34 7 5 3 91 23 76 77 86 84 92 50 51 45 61 30 66 35 1 10 79 39 6 80 82 43 88 75 60 38 87 40 8 19 56 72 65 37...
output:
80
result:
ok 1 number(s): "80"
Test #5:
score: 0
Accepted
time: 2ms
memory: 18004kb
input:
10 10 22 71 28 19 15 47 31 88 95 85 56 79 87 43 96 39 45 97 83 36 6 21 98 34 65 91 58 62 41 42 26 37 74 8 27 55 84 75 20 35 49 24 51 32 50 68 52 5 10 11 25 73 38 92 63 67 64 13 46 78 57 53 23 54 16 99 17 40 82 30 61 81 48 7 86 4 3 60 93 76 90 18 29 44 1 100 2 69 9 12 80 70 33 94 66 72 77 14 59 89 22...
output:
24
result:
ok 1 number(s): "24"
Test #6:
score: 0
Accepted
time: 0ms
memory: 15888kb
input:
10 10 35 58 83 13 75 51 32 97 76 6 63 96 52 77 65 59 90 86 68 9 22 16 56 74 100 91 44 66 8 79 28 21 17 94 31 60 25 24 64 14 55 71 81 67 53 7 95 41 30 40 78 54 48 10 34 47 3 70 98 38 61 89 42 49 50 20 45 18 62 27 73 15 37 84 57 33 88 2 82 72 85 29 80 26 43 39 92 1 93 19 99 11 5 69 87 12 46 4 23 36 97...
output:
24
result:
ok 1 number(s): "24"
Test #7:
score: 0
Accepted
time: 2ms
memory: 15920kb
input:
10 10 15 53 47 95 2 80 94 98 17 99 34 37 89 59 49 41 25 29 79 84 45 42 19 20 70 40 4 73 58 76 51 81 87 65 3 10 1 93 27 38 39 96 13 63 8 30 35 68 52 5 75 83 18 88 9 100 92 14 22 46 32 72 69 6 11 12 90 86 62 48 82 61 60 74 71 44 43 16 23 57 26 21 91 64 77 33 55 24 54 78 28 7 36 85 50 31 56 67 97 66 45...
output:
60
result:
ok 1 number(s): "60"
Test #8:
score: 0
Accepted
time: 2ms
memory: 15936kb
input:
10 10 11 17 94 61 73 42 79 40 2 7 35 96 24 100 85 46 22 9 98 97 51 44 27 14 48 21 33 36 45 34 56 4 39 6 63 75 74 54 57 66 59 37 10 93 58 78 89 72 55 30 64 32 68 83 38 90 99 67 69 95 49 41 91 71 5 19 26 47 80 52 84 70 13 20 77 12 8 86 88 82 16 43 50 25 53 1 29 81 76 92 28 18 31 87 3 15 65 60 62 23 11...
output:
4
result:
ok 1 number(s): "4"
Test #9:
score: 0
Accepted
time: 0ms
memory: 15816kb
input:
12 12 19 131 48 26 21 108 103 84 110 144 49 24 22 35 8 47 34 138 7 142 100 13 79 126 82 31 94 58 74 61 56 99 101 96 67 109 81 5 43 38 54 10 83 107 16 50 133 97 59 68 72 117 113 14 116 6 4 44 111 91 28 69 136 135 71 30 129 52 139 25 125 9 88 40 1 51 86 66 62 76 105 78 102 70 87 137 64 93 41 118 124 3...
output:
4
result:
ok 1 number(s): "4"
Test #10:
score: 0
Accepted
time: 2ms
memory: 15956kb
input:
12 12 144 73 133 126 22 86 83 13 120 62 101 39 26 7 141 125 3 40 99 140 114 28 68 27 42 17 85 35 71 50 46 45 5 14 47 2 49 9 88 32 18 97 29 95 8 109 1 76 111 48 60 132 20 115 138 43 135 112 4 92 55 143 127 52 117 36 84 107 110 15 105 104 74 37 102 129 108 23 98 38 19 122 6 59 33 90 118 89 116 11 56 1...
output:
16
result:
ok 1 number(s): "16"
Test #11:
score: 0
Accepted
time: 1ms
memory: 15944kb
input:
10 10 89 28 86 9 59 70 49 5 8 47 65 84 42 99 27 44 90 62 24 25 12 95 81 21 58 66 37 76 20 68 34 87 77 18 26 11 61 45 96 51 60 80 64 32 53 19 78 38 30 3 13 63 79 48 46 82 55 93 15 40 100 41 71 36 16 83 14 52 98 10 73 17 91 50 7 67 6 75 74 1 22 43 33 54 31 72 85 88 39 23 4 92 2 35 69 57 94 56 29 97 72...
output:
2
result:
ok 1 number(s): "2"
Test #12:
score: 0
Accepted
time: 129ms
memory: 70620kb
input:
1000 1000 145656 791628 740559 132604 88206 427138 947611 103465 802534 882213 161554 408446 198824 194485 228763 373358 414907 364727 747248 222571 971478 217962 525156 244261 193496 681387 978458 994637 413901 206046 663949 547415 151899 508035 778005 977645 576922 604407 537722 999374 62502 54059...
output:
1000000
result:
ok 1 number(s): "1000000"
Test #13:
score: 0
Accepted
time: 130ms
memory: 73228kb
input:
1000 1000 834264 617630 804453 55758 887929 710187 983995 537648 412974 189468 702697 792339 791361 697740 501608 611911 695540 929085 106655 515172 67349 499726 855097 527613 193542 954358 868521 103306 178517 645631 689409 588682 426918 965958 347115 180933 933208 129629 471469 236249 560194 86873...
output:
888000
result:
ok 1 number(s): "888000"
Test #14:
score: 0
Accepted
time: 124ms
memory: 72632kb
input:
1000 1000 894204 922634 641738 426212 799590 748573 191782 123346 800500 11798 525443 111932 224897 541191 482575 709497 534061 940819 479215 375276 799859 936003 825761 629886 13572 192641 615652 931690 906911 937429 279445 395821 896441 78960 492938 865513 234692 905707 416821 535693 639924 841267...
output:
888000
result:
ok 1 number(s): "888000"
Test #15:
score: 0
Accepted
time: 128ms
memory: 71684kb
input:
1000 1000 587421 301118 179182 275437 386302 457395 980201 35204 779891 445474 89083 371943 109388 209211 739330 17326 87415 259919 692438 110621 305268 271211 814752 959558 150036 63482 95294 31028 906066 442717 512281 879496 281289 267298 780720 18122 685329 40044 77451 422869 888408 845508 158633...
output:
688000
result:
ok 1 number(s): "688000"
Test #16:
score: 0
Accepted
time: 133ms
memory: 70052kb
input:
1000 1000 356811 668674 14314 764133 586936 143976 561737 981634 334512 234317 600793 480808 661957 453519 18265 982637 930584 159346 681415 331241 386870 402687 601019 503555 824478 178469 735809 387250 110848 420771 188261 437252 829209 939355 612968 736035 313395 223141 574827 521304 587503 74856...
output:
337000
result:
ok 1 number(s): "337000"
Test #17:
score: 0
Accepted
time: 130ms
memory: 70124kb
input:
1000 1000 706920 573644 154412 106649 788788 770372 420639 742343 128604 314275 975043 784488 275223 498450 374838 47549 31083 909214 301413 226517 910969 334729 337267 268116 152406 154471 265087 351382 253268 5379 657673 42372 494849 174559 99124 589781 700857 328814 868149 984374 544412 172913 78...
output:
524790
result:
ok 1 number(s): "524790"
Test #18:
score: 0
Accepted
time: 124ms
memory: 71432kb
input:
1000 1000 525291 510203 545009 626292 879915 594465 804288 136588 470495 743908 489872 920978 77675 474856 967001 383814 193855 662307 561494 2309 799135 974599 525921 378897 5141 860884 680521 67789 266807 759551 233363 356431 209004 269199 580474 814531 273488 986067 415832 737876 415955 508357 95...
output:
19456
result:
ok 1 number(s): "19456"
Test #19:
score: 0
Accepted
time: 120ms
memory: 72288kb
input:
996 996 927299 347267 882375 22381 920813 939466 272944 584277 576812 237584 53973 308598 501605 300807 959516 838795 57580 857245 432334 629436 708888 787055 196710 120158 586102 111373 133023 742733 550082 448294 381569 406805 544071 818981 583694 23498 696693 334993 196043 91937 864449 559124 660...
output:
2544
result:
ok 1 number(s): "2544"
Test #20:
score: 0
Accepted
time: 116ms
memory: 71900kb
input:
996 996 782359 904764 55471 664477 653508 48721 793225 158889 136958 762830 279660 436974 560985 503753 668793 125335 715876 337839 826187 181992 175569 132138 861510 148948 411469 955141 614086 903043 704790 692450 615696 624789 105121 970361 199883 653169 658177 416684 203865 857561 705686 427983 ...
output:
38038
result:
ok 1 number(s): "38038"
Test #21:
score: 0
Accepted
time: 138ms
memory: 67152kb
input:
1000 1000 242649 672548 111571 431222 708158 721710 26878 888699 563496 279408 191876 422158 740899 397577 563772 240496 178951 84939 984745 849149 799272 518207 685039 358973 395701 439509 979159 132076 74966 801592 214174 264148 918969 452803 125081 251092 873721 7791 772682 601238 802704 591771 5...
output:
2
result:
ok 1 number(s): "2"
Extra Test:
score: -3
Extra Test Failed : Wrong Answer on 1
time: 2ms
memory: 15808kb
input:
2 2 1 2 3 4 1 4 2 3
output:
2
result:
wrong answer 1st numbers differ - expected: '1', found: '2'