Submission #91424

#	Time	Username	Problem	Language	Result	Execution time	Memory
91424		Vardanyan	Bomb (IZhO17_bomb)	C++14	31 / 100	1098 ms	74364 KiB

bomb

#include<bits/stdc++.h>

using namespace std;
const int N = 2505;
int a[N][N];
int pref[N][N];
int pref2[N][N];
int calc1(int x1,int y1,int x2,int y2){
    return pref[x2][y2]-pref[x2][y1-1]-pref[x1-1][y2]+pref[x1-1][y1-1];
}
int calc2(int x1,int y1,int x2,int y2){
    return pref2[x2][y2]-pref2[x2][y1-1]-pref2[x1-1][y2]+pref2[x1-1][y1-1];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            char c;
            scanf(" %c",&c);
            a[i][j] = (c == '1');
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            pref[i][j] = pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
        }
    }
    int ans = 1;
    for(int p = n;p>=1;p--){
        int lo = 1;
        int hi = m;
        int as = -1;
        while(lo<=hi){
            int mid = (lo+hi)/2;
            int x = p;
            int y = mid;
            bool f = true;
            for(int i = 1;i<=n;i++)
            for(int j = 1;j<=m;j++) pref2[i][j] = 0;
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=m;j++){
                  //  if(a[i][j]!=1) continue;
                    pref2[i][j] = pref2[i-1][j]+pref2[i][j-1]-pref2[i-1][j-1];
                    if(i+x-1<=n && j+y-1<=m){
                        if(calc1(i,j,i+x-1,j+y-1) == mid*p){
                            pref2[i][j] = pref2[i-1][j]+pref2[i][j-1]-pref2[i-1][j-1]+1;
                        }
                    }
                    if(a[i][j] == 0) continue;
                    int x1 = i-x+1;
                    int y1 = j-y+1;
                    x1 = max(1,x1);
                    y1 = max(1,y1);
                    if(calc2(x1,y1,i,j) == 0){
                        f = false;
                        break;
                    }
                }
            }
            if(f){
              //  F = true;
              //  break;
              lo = mid+1;
              as = mid;
              continue;
            }
            swap(x,y);
            f = true;
            for(int i = 1;i<=n;i++)
            for(int j = 1;j<=m;j++) pref2[i][j] = 0;
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=m;j++){
                 //   if(a[i][j]!=1) continue;
                    pref2[i][j] = pref2[i-1][j]+pref2[i][j-1]-pref2[i-1][j-1];
                    if(i+x-1<=n && j+y-1<=m){
                        if(calc1(i,j,i+x-1,j+y-1) == mid*p){
                            pref2[i][j] = pref2[i-1][j]+pref2[i][j-1]-pref2[i-1][j-1]+1;
                        }
                    }
                    if(a[i][j] == 0) continue;
                    int x1 = i-x+1;
                    int y1 = j-y+1;
                    x1 = max(1,x1);
                    y1 = max(1,y1);
                    if(calc2(x1,y1,i,j) == 0){
                        f = false;
                        break;
                    }
                }
            }

            if(f){
             //   F = true;
               // break;
                lo = mid+1;
                as = mid;
                continue;
            }
            hi = mid-1;
        }
        if(as == -1) continue;
        ans = max(ans,as*p);
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
bomb.cpp:21:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c",&c);
             ~~~~~^~~~~~~~~~

• Subtask 1: 31 / 100