QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #210643 | #7051. Largest Common Submatrix | yangqb | TL | 2ms | 18284kb | C++20 | 4.0kb | 2023-10-11 18:00:52 | 2023-10-11 18:00:53 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
//#define int long long
#define endl '\n'
const int N=1e6+5, mod=998244353;
inline char nc() {
static char buf[1000000], * p1 = buf, * p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int &sum) {
char ch = nc(); sum = 0;
while (!(ch >= '0' && ch <= '9')) ch = nc();
while (ch >= '0' && ch <= '9') sum = (sum << 3ll) + (sum << 1ll) + (ch - 48ll), ch = nc();
}
int a[1005][1005], b[1005][1005];
int ra[N], rb[N];
int ca[N], cb[N];
int d[1005][1005];
void solve(){
int n, m;
read(n), read(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
read(a[i][j]);
ra[a[i][j]] = i;
ca[a[i][j]] = j;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
read(b[i][j]);
rb[b[i][j]] = i;
cb[b[i][j]] = j;
}
}
int ans = 1;
for(int i=1;i<=n;i++){
//vector<int> d(m+1);
for(int j=1;j<=m;j++){
if(d[i][j]) continue;
int k = i;
while(k<n&&cb[a[k][j]]==cb[a[k+1][j]]&&rb[a[k][j]]+1==rb[a[k+1][j]]) k++;
for(int l=i;l<=k;l++){
d[l][j] = k-l+1;
}
}
for(int j=1;j<=m;j++){
int k = j, mx = a[i][j];
while(k<m&&rb[a[i][k]]==rb[a[i][k+1]]&&cb[a[i][k]]+1==cb[a[i][k+1]]) k++, mx = max(mx,a[i][k]);
if((k-j+1)*mx<=ans){
j = k;
continue;
}
for(int l=j;l<=k;l++){
int mi = d[i][l];
ans = max(ans,d[i][l]);
for(int r=l;r<=k;r++){
mi = min(mi,d[i][r]);
ans = max(ans,mi*(r-l+1));
}
}
j = k;
}
}
printf("%d\n",ans);
}
int main(){
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
// int T;
// cin>>T;
// while(T--)
solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 16148kb
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: 0ms
memory: 18164kb
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: 2ms
memory: 16196kb
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: 18168kb
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: 0ms
memory: 18228kb
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: 16304kb
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: 18164kb
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: 0ms
memory: 18220kb
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: 2ms
memory: 18284kb
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: 0ms
memory: 18236kb
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: 0ms
memory: 18204kb
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: -100
Time Limit Exceeded
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