제출 #87293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
87293		Yaroslaff	Bomb (IZhO17_bomb)	C++14	50 / 100	457 ms	132096 KiB

bomb

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define ll long long
#define int short int
#define ld long double
#define null nullptr
#define endl '\n'

using namespace std;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

//const int M = 1e9 + 7;
const int N = 2502;

int n, m, x[N][N], l[N][N], r[N][N], res[N], ans;
string s[N];

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifdef LOCAL
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
//#else
//    freopen("bomb.in","r",stdin);
//    freopen("bomb.out","w",stdout);
#endif
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> s[i];res[i + 1] = N;
        for (int j = 0; j < m; j++)
            x[i][j] = s[i][j] - '0';
    }
    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++){
        if (!x[i][j]) l[i][j] = 0;
        else l[i][j] = (j ? l[i][j - 1] : 0) + 1;
    }
    for (int i = n - 1; i >= 0; i--)
    for (int j = m - 1; j >= 0; j--){
        if (!x[i][j]) r[i][j] = 0;
        else r[i][j] = r[i][j + 1] + 1;
    }
    for (int j = 0; j < m; j++){
        int tl = N;
        int tr = N;
        int p = -1;
        for (int i = 0; i <= n; i++){
            if (i != n && x[i][j] == 1){
                res[1] = min(res[1], (int)(l[i][j] + r[i][j] - 1));
                int len = i - p;
                tl = min(tl, l[i][j]);
                tr = min(tr, r[i][j]);
                res[len] = min(res[len], (int)(tl + tr - 1));
            }
            if (i == n || x[i][j] == 0){
                int l = i - p;
//                cerr << l << endl;
                if (l != 1) res[l] = 0;
                tl = tr = N;
                p = i;
            }
        }
        tl = N;
        tr = N;
        p = n;
        for (int i = n - 1; i >= -1; i--){
            if (i != -1 && x[i][j] == 1){
                res[1] = min(res[1], (int)(l[i][j] + r[i][j] - 1));
                int len = p - i;
                tl = min(tl, l[i][j]);
                tr = min(tr, r[i][j]);
                res[len] = min(res[len], (int)(tl + tr - 1));
            }
            if (i == -1 || x[i][j] == 0){
                int l = p - i;
//                cerr << l << endl;
                if (l != 1) res[l] = 0;
                tl = tr = N;
                p = i;
            }
        }
    }
    for (int i = 2; i <= n; i++)
        res[i] = min(res[i], res[i - 1]);
    for (int i = 1; i <= n; i++)
        ans = max(ans, (int)(i*res[i]));
    cout << ans;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bomb.cpp:22:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

• Subtask 1: 50 / 100