oj.uz

Submission #441813

# Submission time Handle Problem Language Result Execution time Memory
441813 2021-07-06T09:05:45 Z leaked Bomb (IZhO17_bomb) C++14
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

#define vec vector
#define sz(x) (int)x.size()
#define m_p make_pair
#define f first
#define s second
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
auto rng=bind(uniform_int_distribution<int>(1,1e9),mt19937(time(0)));
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=2503;
int dp[N][N];
int a[N][N];
int n,m;
int check(int x){
    vec<vec<int>>lol(n+2,vec<int>(m+2,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(dp[i][j]>=x){
                lol[i][j]++;lol[i][j+x]--;
                lol[i+x][j]--;
                lol[i+x][j+x]++;
            }
        }
    }
    int ok=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
//            cerr<<lol[i][j]<<' ';
            lol[i][j]+=lol[i-1][j]+lol[i][j-1]-lol[i-1][j-1];
//            cerr<<lol[i][j]<<' ';
            if(a[i][j]){
                ok&=(lol[i][j]>0);
//                if(!lol[i][j]){
//                    cout<<
//                }
            }

//            cout<<endl;
        }
//        cout<<endl;
    }
    return ok;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ifstream cin("bomb.in");
    ofstream cout("bomb.out");
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        for(int j=0;j<m;j++){
            a[i][j+1]=s[j]-'0';
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;j--){
            if(a[i][j]){
                dp[i][j]=min({dp[i+1][j],dp[i][j+1],dp[i+1][j+1]})+1;
            }
        }
    }
//    cout<<check(2);
//    return 0;
    int l=1,r=min(n,m)+1;
    while(l!=r){
        int tm=(l+r)>>1;
        if(check(tm)) l=tm+1;
        else r=tm;
    }
    l--;
//    cout<<l<<endl;
//    return 0;
    int f=l,s=l;
    int o=2e9;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=(dp[i][j]>=l);
//            cerr<<dp[i][j]<<' ';
//            if(i==8 && j==11){
//                cout<<dp[i][j]<<endl;
//            }
        }
//        cerr<<endl;
    }
//    return 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!a[i][j]) continue;
            int k=j;
            while(k<=m && a[i][k]){
                k++;
            }
//            if(k-j-1==0){
//                cout<<i<<' '<<j<<endl;
//            }
            umin(o,k-j-1);
            j=k;
        }
    }
//    cout<<o<<endl;
    s+=o;
    o=2e9;
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            if(!a[i][j]) continue;
            int k=i;
            while(k<=n && a[k][j]){
                k++;
            }
            umin(o,k-i-1);
//            if(k-i-1==0){
//                cout<<i<<' '<<j<<endl;
//            }
//            cout<<k-i-1<<endl;
            i=k;
//            cerr<<k-i-1<<endl;
        }
    }
    f+=o;
    cout<<1ll*f*s;
    return 0;
}

/*
10
2 1 2 2 1 1 3 2 5 5
*/

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Incorrect 0 ms 332 KB Output isn't correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Incorrect 1 ms 204 KB Output isn't correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Incorrect 0 ms 204 KB Output isn't correct
9 Incorrect 0 ms 332 KB Output isn't correct
10 Incorrect 1 ms 332 KB Output isn't correct
11 Incorrect 0 ms 332 KB Output isn't correct
12 Incorrect 0 ms 332 KB Output isn't correct
13 Incorrect 1 ms 332 KB Output isn't correct
14 Incorrect 0 ms 332 KB Output isn't correct
15 Incorrect 1 ms 332 KB Output isn't correct
16 Incorrect 0 ms 332 KB Output isn't correct
17 Incorrect 0 ms 332 KB Output isn't correct
18 Incorrect 0 ms 332 KB Output isn't correct
19 Incorrect 0 ms 332 KB Output isn't correct
20 Incorrect 0 ms 332 KB Output isn't correct
21 Incorrect 1 ms 204 KB Output isn't correct
22 Incorrect 1 ms 332 KB Output isn't correct
23 Incorrect 0 ms 332 KB Output isn't correct
24 Incorrect 0 ms 332 KB Output isn't correct
25 Incorrect 1 ms 332 KB Output isn't correct
26 Incorrect 1 ms 204 KB Output isn't correct
27 Incorrect 1 ms 332 KB Output isn't correct
28 Incorrect 0 ms 204 KB Output isn't correct
29 Incorrect 1 ms 332 KB Output isn't correct
30 Incorrect 1 ms 204 KB Output isn't correct
31 Incorrect 1 ms 332 KB Output isn't correct
32 Incorrect 1 ms 204 KB Output isn't correct
33 Incorrect 0 ms 332 KB Output isn't correct
34 Incorrect 1 ms 332 KB Output isn't correct
35 Incorrect 1 ms 332 KB Output isn't correct
36 Incorrect 1 ms 332 KB Output isn't correct
37 Incorrect 0 ms 204 KB Output isn't correct
38 Incorrect 0 ms 332 KB Output isn't correct
39 Incorrect 0 ms 332 KB Output isn't correct
40 Incorrect 0 ms 332 KB Output isn't correct
41 Incorrect 1 ms 204 KB Output isn't correct
42 Incorrect 0 ms 332 KB Output isn't correct
43 Incorrect 1 ms 348 KB Output isn't correct
44 Incorrect 0 ms 332 KB Output isn't correct
45 Incorrect 0 ms 332 KB Output isn't correct
46 Incorrect 0 ms 332 KB Output isn't correct
47 Incorrect 1 ms 332 KB Output isn't correct
48 Incorrect 0 ms 332 KB Output isn't correct
49 Incorrect 1 ms 332 KB Output isn't correct
50 Incorrect 1 ms 332 KB Output isn't correct
51 Incorrect 0 ms 204 KB Output isn't correct
52 Incorrect 0 ms 332 KB Output isn't correct
53 Incorrect 1 ms 332 KB Output isn't correct
54 Incorrect 0 ms 332 KB Output isn't correct
55 Incorrect 0 ms 332 KB Output isn't correct
56 Incorrect 0 ms 332 KB Output isn't correct
57 Incorrect 1 ms 204 KB Output isn't correct
58 Incorrect 1 ms 332 KB Output isn't correct
59 Incorrect 0 ms 332 KB Output isn't correct
60 Incorrect 1 ms 332 KB Output isn't correct
61 Incorrect 0 ms 204 KB Output isn't correct
62 Incorrect 0 ms 204 KB Output isn't correct
63 Incorrect 0 ms 332 KB Output isn't correct
64 Incorrect 1 ms 332 KB Output isn't correct
65 Incorrect 1 ms 332 KB Output isn't correct
66 Incorrect 0 ms 204 KB Output isn't correct
67 Incorrect 0 ms 332 KB Output isn't correct
68 Incorrect 0 ms 332 KB Output isn't correct
69 Incorrect 0 ms 204 KB Output isn't correct
70 Incorrect 0 ms 332 KB Output isn't correct
71 Incorrect 1 ms 332 KB Output isn't correct
72 Incorrect 1 ms 204 KB Output isn't correct
73 Incorrect 1 ms 332 KB Output isn't correct
74 Incorrect 1 ms 332 KB Output isn't correct
75 Incorrect 1 ms 332 KB Output isn't correct
76 Incorrect 1 ms 332 KB Output isn't correct
77 Incorrect 0 ms 204 KB Output isn't correct
78 Incorrect 0 ms 332 KB Output isn't correct
79 Incorrect 0 ms 204 KB Output isn't correct
80 Incorrect 0 ms 332 KB Output isn't correct
81 Incorrect 0 ms 332 KB Output isn't correct
82 Incorrect 0 ms 332 KB Output isn't correct
83 Incorrect 0 ms 204 KB Output isn't correct
84 Incorrect 0 ms 332 KB Output isn't correct
85 Incorrect 1 ms 332 KB Output isn't correct
86 Incorrect 0 ms 332 KB Output isn't correct
87 Incorrect 1 ms 332 KB Output isn't correct
88 Incorrect 0 ms 204 KB Output isn't correct
89 Incorrect 0 ms 204 KB Output isn't correct
90 Incorrect 0 ms 204 KB Output isn't correct
91 Incorrect 0 ms 332 KB Output isn't correct
92 Incorrect 0 ms 204 KB Output isn't correct
93 Incorrect 0 ms 332 KB Output isn't correct
94 Incorrect 0 ms 332 KB Output isn't correct
95 Incorrect 1 ms 332 KB Output isn't correct
96 Incorrect 0 ms 268 KB Output isn't correct
97 Incorrect 1 ms 332 KB Output isn't correct
98 Incorrect 0 ms 332 KB Output isn't correct
99 Incorrect 0 ms 332 KB Output isn't correct
100 Incorrect 0 ms 332 KB Output isn't correct