Submission #1605976


Source Code Expand

#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <string>
 
#define INFLL 2000000000000000000
#define INF 2000000000
#define MOD 1000000007
#define PI acos(-1.0)
 
using namespace std;
 
typedef pair <int, int> pii;
typedef long long ll;
typedef vector <ll> vll;

bool isGood[2000][2000];
bool board[2000][2000];
int up[2000][2000];
int n, m;
int t[8000];
int curRow;

void build(int v, int l, int r) {
	if (l == r) {
		t[v] = up[curRow][l];
		return;
	}
	int mid = (l + r) / 2;
	build(2 * v, l, mid);
	build(2 * v + 1, mid + 1, r);
	t[v] = min(t[2 * v], t[2 * v + 1]);
}

int get(int v, int l, int r, int wl, int wr) {
	if (wl > wr)
		return INF;
	if (wl == l && wr == r) {
		return t[v];
	}
	int mid = (l + r) / 2;
	return min(get(2 * v, l, mid, wl, min(mid, wr)), get(2 * v + 1, mid + 1, r, max(mid + 1, wl), wr));
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < str.length(); j++) {
			board[i][j] = (str[j] == '#');
		}
	}
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < m - 1; j++) {
			int cnt = 0;
			for (int x = 0; x < 2; x++)
				for (int y = 0; y < 2; y++)
					if (board[i + x][j + y])
						cnt++;
			if (cnt % 2 == 0)
				isGood[i][j] = true;
			else
				isGood[i][j] = false;
		}
	}
	m--;
	n--;
	for (int i = 0; i < m; i++) 
		if (isGood[0][i]) up[0][i] = 1;
		else up[0][i] = 0;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (isGood[i][j])
				up[i][j] = up[i - 1][j] + 1;
			else
				up[i][j] = 0;
		}
	}
	// for (int i = 0; i < n; i++) {
	// 	for (int j = 0; j < m; j++)
	// 		cout << up[i][j] << " ";
	// 	cout << endl;
	// }
	int ans = -INF;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 8000; j++)
			t[j] = INF;
		curRow = i;
		build(1, 0, m - 1);
		for (int j = 0; j < m; j++) {
			int aa = -1, bb = m;
			int ll = 0, rr = j - 1;
			while (ll <= rr) {
				int mid = (ll + rr) / 2;
				if (get(1, 0, m - 1, mid, j - 1) < up[i][j]) {
					aa = mid;
					ll = mid + 1;
				} else rr = mid - 1;
			}
			ll = j + 1, rr = m - 1;
			while (ll <= rr) {
				int mid = (ll + rr) / 2;
				if (get(1, 0, m - 1, j + 1, mid) < up[i][j]) {
					bb = mid;
					rr = mid - 1;
				} else ll = mid + 1;
			}
			ans = max(ans, (bb - aa) * (up[i][j] + 1));
			//cout << i << " " << j << " " << aa << " " << bb << endl;
		}
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task F - Flip and Rectangles
User spiderbatman
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2645 Byte
Status WA
Exec Time 2104 ms
Memory 23808 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 3
AC × 9
WA × 1
TLE × 30
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 WA 12 ms 22784 KB
10.txt TLE 2104 ms 23680 KB
11.txt TLE 2103 ms 23680 KB
12.txt TLE 2104 ms 23680 KB
13.txt TLE 2103 ms 23680 KB
14.txt TLE 2103 ms 23680 KB
15.txt TLE 2104 ms 23680 KB
16.txt TLE 2104 ms 23680 KB
17.txt TLE 2103 ms 23680 KB
18.txt TLE 2104 ms 23680 KB
19.txt TLE 2104 ms 23680 KB
2.txt AC 8 ms 4352 KB
20.txt TLE 2104 ms 23680 KB
21.txt TLE 2103 ms 23680 KB
22.txt TLE 2103 ms 23680 KB
23.txt TLE 2103 ms 23680 KB
24.txt TLE 2103 ms 23680 KB
25.txt TLE 2103 ms 23680 KB
26.txt TLE 2104 ms 23680 KB
27.txt TLE 2104 ms 23680 KB
28.txt TLE 2104 ms 23680 KB
29.txt TLE 2103 ms 23680 KB
3.txt TLE 2104 ms 23680 KB
30.txt TLE 2104 ms 23680 KB
31.txt TLE 2104 ms 23808 KB
32.txt TLE 2103 ms 23680 KB
33.txt TLE 2103 ms 23680 KB
34.txt TLE 2103 ms 23680 KB
4.txt TLE 2103 ms 23680 KB
5.txt AC 12 ms 22784 KB
6.txt AC 8 ms 4352 KB
7.txt TLE 2104 ms 23680 KB
8.txt TLE 2103 ms 23680 KB
9.txt TLE 2104 ms 23808 KB
sample1.txt AC 2 ms 4352 KB
sample2.txt AC 2 ms 4352 KB
sample3.txt AC 2 ms 4352 KB