QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#153750#7051. Largest Common SubmatrixPetroTarnavskyi#RE 2ms3612kbC++171.9kb2023-08-30 21:09:382023-08-30 21:09:39

Judging History

你现在查看的是最新测评结果

  • [2023-08-30 21:09:39]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:3612kb
  • [2023-08-30 21:09:38]
  • 提交

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";
}

详细

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...

output:


result: