Submission #2858258


Source Code Expand

/*
进行列的翻转操作之后,合法的矩形一定满足每一行的颜色都相等(无所谓黑白,因为可以有行操作来调整)
每一行颜色相等等价于该行任意相邻两个格子颜色相等,等价于两个格子对应的列的翻转情况是 / 否相等
相当于有一些限制,同时两个相邻格子对应的列在每一行的限制都相等 
故可以直接转化成一个最大子矩形问题 
*/

#include <stack>
#include <cstdio>
#include <algorithm>

using namespace std;
const int Max_NM(2050);

int N, M, rev[Max_NM][Max_NM], up[Max_NM][Max_NM];
char S[Max_NM];

void init()
{
	scanf("%d%d", &N, &M);
	for (int i = 1;i <= N;++i)
	{
		scanf("%s", S + 1);
		for (int j = 2;j <= M;++j)
			rev[i][j] = (S[j - 1] != S[j]), up[i][j] = (rev[i][j] == rev[i - 1][j] ? up[i - 1][j] : 0) + 1; 
	}
}

int L[Max_NM], R[Max_NM];
void work()
{
	int Ans(N);
	for (int i = 1;i <= N;++i)
	{
		stack<int> S;
		for (int j = 2;j <= M;++j)
		{
			while (S.empty() == false && up[i][S.top()] > up[i][j])
				R[S.top()] = j - 1, S.pop();
			S.push(j);
		}
		while (S.empty() == false)
			R[S.top()] = M, S.pop();
		for (int j = M;j >= 2;--j)
		{
			while (S.empty() == false && up[i][S.top()] > up[i][j])
				L[S.top()] = j + 1, S.pop();
			S.push(j);
		}
		while (S.empty() == false)
			L[S.top()] = 2, S.pop();
		for (int j = 2;j <= M;++j)
			Ans = max(Ans, up[i][j] * (R[j] - L[j] + 2));
	}
	printf("%d", Ans);
}

int main()
{
	init();
	work();
	return 0;
}

Submission Info

Submission Time
Task F - Flip and Rectangles
User Created_equal
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1545 Byte
Status AC
Exec Time 123 ms
Memory 33024 KB

Compile Error

./Main.cpp: In function ‘void init()’:
./Main.cpp:20:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
./Main.cpp:23:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S + 1);
                     ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 3
AC × 40
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt AC 8 ms 32000 KB
10.txt AC 103 ms 33024 KB
11.txt AC 37 ms 33024 KB
12.txt AC 62 ms 33024 KB
13.txt AC 63 ms 33024 KB
14.txt AC 64 ms 33024 KB
15.txt AC 65 ms 33024 KB
16.txt AC 65 ms 33024 KB
17.txt AC 64 ms 33024 KB
18.txt AC 111 ms 33024 KB
19.txt AC 76 ms 33024 KB
2.txt AC 2 ms 2304 KB
20.txt AC 82 ms 33024 KB
21.txt AC 81 ms 33024 KB
22.txt AC 80 ms 33024 KB
23.txt AC 91 ms 33024 KB
24.txt AC 60 ms 33024 KB
25.txt AC 60 ms 33024 KB
26.txt AC 118 ms 33024 KB
27.txt AC 108 ms 33024 KB
28.txt AC 102 ms 33024 KB
29.txt AC 61 ms 33024 KB
3.txt AC 123 ms 33024 KB
30.txt AC 64 ms 33024 KB
31.txt AC 65 ms 33024 KB
32.txt AC 66 ms 33024 KB
33.txt AC 66 ms 33024 KB
34.txt AC 66 ms 33024 KB
4.txt AC 123 ms 33024 KB
5.txt AC 8 ms 32000 KB
6.txt AC 2 ms 2304 KB
7.txt AC 116 ms 33024 KB
8.txt AC 116 ms 33024 KB
9.txt AC 102 ms 33024 KB
sample1.txt AC 1 ms 2304 KB
sample2.txt AC 1 ms 2304 KB
sample3.txt AC 1 ms 2304 KB