oj.uz

Submission #441814

# Submission time Handle Problem Language Result Execution time Memory
441814 2021-07-06T09:06:00 Z leaked Bomb (IZhO17_bomb) C++14
52 / 100
 897 ms 80488 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
52.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Correct 13 ms 20532 KB Output is correct
4 Correct 10 ms 20428 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Incorrect 1 ms 460 KB Output isn't correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 452 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Incorrect 1 ms 844 KB Output isn't correct
18 Incorrect 1 ms 716 KB Output isn't correct
19 Correct 1 ms 972 KB Output is correct
20 Incorrect 2 ms 972 KB Output isn't correct
21 Incorrect 1 ms 588 KB Output isn't correct
22 Incorrect 1 ms 844 KB Output isn't correct
23 Correct 2 ms 972 KB Output is correct
24 Correct 1 ms 844 KB Output is correct
25 Incorrect 2 ms 1228 KB Output isn't correct
26 Correct 2 ms 1228 KB Output is correct
27 Correct 10 ms 3764 KB Output is correct
28 Incorrect 8 ms 2672 KB Output isn't correct
29 Incorrect 12 ms 4924 KB Output isn't correct
30 Correct 16 ms 5196 KB Output is correct
31 Correct 13 ms 3972 KB Output is correct
32 Correct 14 ms 4732 KB Output is correct
33 Incorrect 18 ms 5936 KB Output isn't correct
34 Incorrect 7 ms 2764 KB Output isn't correct
35 Incorrect 16 ms 4236 KB Output isn't correct
36 Incorrect 23 ms 6564 KB Output isn't correct
37 Incorrect 1 ms 460 KB Output isn't correct
38 Correct 613 ms 80144 KB Output is correct
39 Incorrect 1 ms 460 KB Output isn't correct
40 Incorrect 78 ms 17260 KB Output isn't correct
41 Incorrect 1 ms 460 KB Output isn't correct
42 Incorrect 2 ms 1228 KB Output isn't correct
43 Correct 753 ms 78132 KB Output is correct
44 Incorrect 19 ms 6348 KB Output isn't correct
45 Incorrect 659 ms 78908 KB Output isn't correct
46 Correct 663 ms 80376 KB Output is correct
47 Incorrect 685 ms 78832 KB Output isn't correct
48 Incorrect 724 ms 80236 KB Output isn't correct
49 Correct 806 ms 80124 KB Output is correct
50 Incorrect 732 ms 80488 KB Output isn't correct
51 Incorrect 741 ms 80248 KB Output isn't correct
52 Incorrect 756 ms 80156 KB Output isn't correct
53 Incorrect 790 ms 79776 KB Output isn't correct
54 Correct 680 ms 73560 KB Output is correct
55 Correct 745 ms 72716 KB Output is correct
56 Correct 653 ms 80192 KB Output is correct
57 Correct 737 ms 70220 KB Output is correct
58 Correct 685 ms 72752 KB Output is correct
59 Correct 692 ms 71204 KB Output is correct
60 Correct 769 ms 76008 KB Output is correct
61 Correct 745 ms 80208 KB Output is correct
62 Correct 841 ms 80292 KB Output is correct
63 Correct 691 ms 80084 KB Output is correct
64 Correct 692 ms 71524 KB Output is correct
65 Correct 751 ms 79572 KB Output is correct
66 Correct 832 ms 78080 KB Output is correct
67 Incorrect 779 ms 80232 KB Output isn't correct
68 Incorrect 789 ms 80392 KB Output isn't correct
69 Correct 733 ms 70060 KB Output is correct
70 Incorrect 410 ms 44780 KB Output isn't correct
71 Correct 639 ms 66424 KB Output is correct
72 Correct 643 ms 69356 KB Output is correct
73 Incorrect 744 ms 69652 KB Output isn't correct
74 Incorrect 733 ms 70424 KB Output isn't correct
75 Correct 693 ms 71084 KB Output is correct
76 Incorrect 687 ms 71628 KB Output isn't correct
77 Incorrect 717 ms 71916 KB Output isn't correct
78 Correct 682 ms 72120 KB Output is correct
79 Correct 649 ms 58428 KB Output is correct
80 Correct 609 ms 59088 KB Output is correct
81 Incorrect 640 ms 59076 KB Output isn't correct
82 Correct 697 ms 73336 KB Output is correct
83 Incorrect 684 ms 73496 KB Output isn't correct
84 Incorrect 601 ms 55944 KB Output isn't correct
85 Incorrect 663 ms 73008 KB Output isn't correct
86 Correct 853 ms 79600 KB Output is correct
87 Incorrect 659 ms 72300 KB Output isn't correct
88 Correct 670 ms 72740 KB Output is correct
89 Incorrect 681 ms 77052 KB Output isn't correct
90 Correct 417 ms 51684 KB Output is correct
91 Incorrect 740 ms 74968 KB Output isn't correct
92 Incorrect 754 ms 75672 KB Output isn't correct
93 Incorrect 897 ms 79308 KB Output isn't correct
94 Incorrect 759 ms 76476 KB Output isn't correct
95 Correct 654 ms 73484 KB Output is correct
96 Correct 662 ms 73424 KB Output is correct
97 Incorrect 849 ms 79476 KB Output isn't correct
98 Incorrect 675 ms 73356 KB Output isn't correct
99 Incorrect 709 ms 76456 KB Output isn't correct
100 Incorrect 816 ms 78884 KB Output isn't correct