# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
917917 | SeDunion | Bomb (IZhO17_bomb) | C++17 | 446 ms | 80428 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
using namespace std;
const int N = 2505;
int a[N][N], ans[N];
int L[N][N], R[N][N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1 ; i <= n ; ++ i) {
for (int j = 1 ; j <= m ; ++ j) {
char c;
cin >> c;
a[i][j] = (c - '0');
}
}
for (int i = 1 ; i <= n ; ++ i) {
ans[i] = m;
}
int lim = n;
for (int rep = 0 ; rep < 2 ; ++ rep) {
for (int i = 1 ; i <= n ; ++ i) {
for (int j = 1 ; j <= m ; ++ j) {
if (a[i][j]) L[i][j] = L[i][j - 1] + 1;
else L[i][j] = 0;
}
for (int j = m ; j >= 1 ; -- j) {
if (a[i][j]) R[i][j] = R[i][j + 1] + 1;
else R[i][j] = 0;
}
}
for (int j = 1 ; j <= m ; ++ j) {
int cnt = 0;
int LX = -1, RX = -1;
for (int i = 1 ; i <= n + 1 ; ++ i) {
if (a[i][j]) {
cnt++;
if (cnt == 1) {
LX = L[i][j], RX = R[i][j];
}
LX = min(LX, L[i][j]), RX = min(RX, R[i][j]);
ans[cnt] = min(ans[cnt], LX + RX - 1);
} else {
if (cnt > 0) lim = min(lim, cnt);
LX = RX = -1;
cnt = 0;
}
}
}
for (int i = 1 ; i <= n / 2 ; ++ i) {
for (int j = 1 ; j <= m ; ++ j) {
swap(a[i][j], a[n - i + 1][j]);
}
}
}
int res = 0;
for (int i = 1 ; i <= lim ; ++ i) {
//cerr << i << " " << ans[i] << endl;
ans[i + 1] = min(ans[i + 1], ans[i]);
res = max(res, ans[i] * i);
}
cout << res;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |