# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
170913 | davitmarg | Bomb (IZhO17_bomb) | C++17 | 964 ms | 80256 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 2505;
int n, m, a[N][N], pr[N][N], nxt[N][N], d[N], Y, X, ans;
int get(int sy, int sx, int y, int x)
{
sy--;
sx--;
return pr[y][x] - pr[sy][x] - pr[y][sx] + pr[sy][sx];
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
char x;
scanf(" %c", &x);
a[i][j] += (x - '0');
pr[i][j] = a[i][j] + pr[i - 1][j] + pr[i][j - 1] - pr[i - 1][j - 1];
}
X = m;
Y = n;
for (int i = 1; i <= n; i++)
for (int j = m; j >= 1; j--)
{
if (a[i][j])
nxt[i][j] = nxt[i][j + 1] + 1;
else
nxt[i][j] = 0;
if (a[i][j - 1] == 0 && a[i][j])
X = min(X, nxt[i][j]);
}
for (int j = 1; j <= m; j++)
{
int y = 0;
for (int i = 1; i <= n; i++)
{
if (a[i][j])
y++;
else
y = 0;
if (a[i][j] && a[i + 1][j] == 0)
Y = min(y, Y);
}
}
for (int i = 1; i <= Y; i++)
d[i] = X;
for (int j = 1; j <= m; j++)
{
int y = 0, x = X;
for (int i = 1; i <= n; i++)
{
if (a[i][j] == 0)
{
y = 0;
x = X;
}
else
{
y++;
x = min(x, nxt[i][j]);
if (get(i - y + 1, j - 1, i, j - 1) != y)
d[y] = min(x, d[y]);
}
//cout << i << " : " << j << " = " << y << " : " << x << endl;
}
}
for (int j = 1; j <= m; j++)
{
int y = 0, x = X;
for (int i = n; i >= 1; i--)
{
if (a[i][j] == 0)
{
y = 0;
x = X;
}
else
{
y++;
x = min(x, nxt[i][j]);
if (get(i, j - 1, i + y - 1, j - 1) != y)
d[y] = min(x, d[y]);
}
//cout << i << " : " << j << " = " << y << " : " << x << endl;
}
}
for (int i = 1; i <= Y; i++)
{
//d[i + 1] = min(d[i + 1], d[i]);
//cout << i << " : " << d[i] << endl;
ans = max(ans, i * d[i]);
}
cout << ans << endl;
return 0;
}
/*
10 8
00000000
00111000
00111000
11111110
11101110
11111110
00111000
00111000
00000000
00000000
6 6
000111
000111
001111
111100
111000
111000
*/
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |