QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#153750 | #7051. Largest Common Submatrix | PetroTarnavskyi# | RE | 2ms | 3612kb | C++17 | 1.9kb | 2023-08-30 21:09:38 | 2023-08-30 21:09:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FILL(a, b) memset(a, b, sizeof(a))
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
struct DSU
{
int n;
VI p, sz;
void init(int _n)
{
n = _n;
p.resize(n);
iota(ALL(p), 0);
sz.assign(n, 1);
}
int find(int v)
{
if (p[v] == v)
{
return v;
}
return p[v] = find(p[v]);
}
void unite(int u, int v)
{
u = find(u);
v = find(v);
if (u == v)
return;
if (sz[u] > sz[v])
swap(u, v);
p[u] = v;
sz[v] += sz[u];
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector a(n, vector<int>(m)), b(n, vector<int>(m)), h(n, vector<int>(m));
vector<int> pos(n * m);
FOR(i, 0, n)
{
FOR(j, 0, m)
{
cin >> a[i][j];
a[i][j]--;
pos[a[i][j]] = m * i + j;
}
}
FOR(i, 0, n)
{
FOR(j, 0, m)
{
cin >> b[i][j];
b[i][j]--;
b[i][j] = pos[b[i][j]];
}
}
DSU dsu;
vector<int> vec;
vector<int> used(m);
int ans = 0;
FOR(i, 0, n)
{
FOR(j, 0, m)
h[i][j] = i > 0 && b[i - 1][j] == b[i][j] - m ? h[i - 1][j] + 1 : 1;
dsu.init(m);
used.assign(m, 0);
for (int l = 0; l < m;)
{
int r = l + 1;
vec = {l};
while (r < m && b[i][r] == b[i][r - 1] + 1)
vec.push_back(r++);
sort(ALL(vec), [&](int j1, int j2){return h[i][j1] > h[i][j2];});
for (int j : vec)
{
used[j] = 1;
if (j - 1 >= l && used[j - 1])
dsu.unite(j, j - 1);
if (j + 1 <= r && used[j + 1])
dsu.unite(j, j + 1);
ans = max(ans, dsu.sz[dsu.find(j)] * h[i][j]);
}
l = r;
}
}
cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3612kb
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: -100
Dangerous Syscalls
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...