# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
334568 | tengiz05 | Bomb (IZhO17_bomb) | C++17 | 326 ms | 87660 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 2505;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int a[N][N], n, m, k;
bool usedup[N][N], usedr[N][N];
int up[N][N], down[N][N];
int ans[N];
vector<int> v[N];
vector<int> s[N];
void solve(int test_case){
int i, j;
cin >> n >> m;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
char c;
cin >> c;
a[i][j] = (c-'0');
}
}
int mx=mod, my=mod;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(a[i][j] == 1){
if(usedup[i][j])continue;
int t = j;
int tmp = 0;
while(t <= m && a[i][t] == 1){
tmp++;
usedup[i][t] = true;
t++;
}mx = min(mx, tmp);
}
}
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(a[i][j] == 1){
if(usedr[i][j])continue;
int t = i;
int tmp = 0;
while(t <= n && a[t][j] == 1){
tmp++;
usedr[t][j] = true;
t++;
}my = min(my, tmp);
}
}
}
if(mx == mod){
mx = 0;
my = 0;
}
/// (mx, my) is greedy answer
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(a[i][j])up[i][j] = up[i-1][j]+a[i][j];
}
}
for(i=n;i>=1;i--){
for(j=1;j<=m;j++){
if(a[i][j])down[i][j] = down[i+1][j]+a[i][j];
}
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(!a[i][j])continue;
int cnt = 1;
int tmp = j;
while(j+1 <= m && a[i][j+1])cnt++,j++;
v[i].pb(tmp);
s[i].pb(cnt);
}
}
for(i=1;i<=m;i++)ans[i] = my;
for(i=1;i<=n;i++){
for(k=0;k<v[i].size();k++){
int j = v[i][k];
int sz = s[i][k];
int a=mod, b=mod, c=0;
for(;sz;sz--, j++){
a = min(a, up[i][j]);
b = min(b, down[i][j]);
c++;
ans[c] = min(ans[c], a+b-1);
}
}
for(k=(int)v[i].size()-1;k>=0;k--){
int sz = s[i][k];
int j = v[i][k]+sz-1;
int a=mod, b=mod, c=0;
for(;sz;sz--, j--){
a = min(a, up[i][j]);
b = min(b, down[i][j]);
c++;
ans[c] = min(ans[c], a+b-1);
}
}
}
// cout << mx << ' ' << my << '\n';
for(i=2;i<=mx;i++)ans[i] = min(ans[i], ans[i-1]);
int res = 0;
// for(i=1;i<=mx;i++)cout << ans[i] << ' '; cout << '\n';
for(i=1;i<=mx;i++)res = max(res, i*ans[i]);
cout << res << '\n';
return;
}
signed main(){
FASTIO;
#define MULTITEST 0
#if MULTITEST
int ___T;
cin >> ___T;
for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
solve(T_CASE);
#else
solve(1);
#endif
return 0;
}
/*
6 6
000111
011111
011111
111000
111000
111000
*/
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |