QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#811507#7051. Largest Common SubmatrixMyK_00LWA 1ms3812kbC++172.8kb2024-12-12 20:10:352024-12-12 20:10:36

Judging History

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

  • [2024-12-12 20:10:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3812kb
  • [2024-12-12 20:10:35]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

int zero_matrix(vector<vector<int>> a) {
    int n = a.size();
    int m = a[0].size();
	for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) a[i][j]=!a[i][j];

    int ans = 0;
    vector<int> d(m, -1), d1(m), d2(m);
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 1)
                d[j] = i;
        }

        for (int j = 0; j < m; ++j) {
            while (!st.empty() && d[st.top()] <= d[j])
                st.pop();
            d1[j] = st.empty() ? -1 : st.top();
            st.push(j);
        }
        while (!st.empty())
            st.pop();

        for (int j = m - 1; j >= 0; --j) {
            while (!st.empty() && d[st.top()] <= d[j])
                st.pop();
            d2[j] = st.empty() ? m : st.top();
            st.push(j);
        }
        while (!st.empty())
            st.pop();

        for (int j = 0; j < m; ++j)
            ans = max(ans, (i - d[j]) * (d2[j] - d1[j] - 1));
    }
    return ans;
}

int solve_row(vector<int> row) {
	int n = row.size();
	vector<array<int,2> > a(n);
	vector<int> l(n,-1);
	vector<int> r(n,-1);
	for(int i=0; i<n; ++i) a[i] = {row[i],i};
	sort(a.rbegin(),a.rend());
	int ans=0;
	for(auto [v,i]: a) {
		l[i]=r[i]=i;
		if(i&&l[i-1]!=-1) l[i]=l[i-1];
		if(i<n-1&&r[i+1]!=-1) r[i]=r[i+1];
		r[l[i]]=r[i];
		l[r[i]]=l[i];
		ans=max(ans, (r[i]-l[i]+1)*v);
	}
	return ans;
}

int solve(vector<vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	for(int i=n-2; i>=0; --i) {
		for(int j=0; j<m; ++j) {
			a[i][j] = a[i][j]?1+a[i+1][j]:0;
		}
	}
	int ans = 0;
	for(int i=0; i<n; ++i) {
		ans=max(ans,solve_row(a[i]));
	}
	return ans;
}

int solve_slow(vector<vector<int> > a) {
	int n = a.size(), m = a[0].size();
	vector<vector<int> > v(n+1,vector<int>(m+1,0));
	for(int i=n-1; i>=0; --i) for(int j=m-1; j>=0; --j) {
		v[i][j]=a[i][j]+v[i+1][j]+v[i][j+1]-v[i+1][j+1];
	}
	int ans=0;
	for(int i1=0; i1<n; ++i1) {
		for(int j1=0; j1<m; ++j1) {
			for(int i2=i1+1; i2<=n; ++i2) {
				for(int j2=j1+1; j2<=m; ++j2) {
					int s = v[i1][j1]-v[i2][j1]-v[i1][j2]+v[i2][j2];
					int a = (i2-i1)*(j2-j1);
					if(a==s) ans = max(ans,a);
				}
			}
		}
	}
	return ans;
}

signed main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	int n,m;
	cin>>n>>m;
	vector<vector<int> > a(n,vector<int>(m));
	for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) cin>>a[i][j];
	for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) {
		int bij;
		cin>>bij;
		a[i][j]=(a[i][j]==bij);
	}
	cout<<zero_matrix(a)<<endl;
	return 0;

	/*
	srand(4);
	int n=19,m=19;
	while(1) {
		vector<vector<int> > a(n,vector<int>(m));
		for(int i=0; i<n; ++i) for(int j=0; j<m; ++j) a[i][j]=rand()%4==0;
		if(solve(a)!=solve_slow(a)) {
			cerr<<"found"<<endl;
			return 0;
		}
	}
	return 0;
	*/
}


詳細信息

Test #1:

score: 100
Accepted
time: 1ms
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: 0
Accepted
time: 0ms
memory: 3608kb

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: 3528kb

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: 0ms
memory: 3540kb

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: -100
Wrong Answer
time: 0ms
memory: 3812kb

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:

10

result:

wrong answer 1st numbers differ - expected: '24', found: '10'