Submission #37407

#	Time	Username	Problem	Language	Result	Execution time	Memory
37407		top34051	Bomb (IZhO17_bomb)	C++14	21 / 100	1000 ms	131072 KiB

bomb

#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 2505;

int n,m;
int p[maxn][maxn];
vector<pii> con[maxn];
set<pii> itv[maxn];
multiset<int> len;

void upd(int x,pii val,int type) {
    if(type==0) {
//        printf("DEL [%d, %d]\n",val.X,val.Y);
        len.erase(len.find(val.Y-val.X+1));
        itv[x].erase(val);
    }
    else {
//        printf("ADD [%d, %d]\n",val.X,val.Y);
        len.insert(val.Y-val.X+1);
        itv[x].insert(val);
    }
}
void add(int x,int y) {
    int l,r;
    set<pii>::iterator L,R;
    upd(x,{y,y},1);
    l = r = y;
    L = R = itv[x].find({y,y});
    if(L!=itv[x].begin()) {
        --L;
        if(L->Y+1==y) {
            l = L->X;
            upd(x,*L,0);
        }
    }
    ++R;
    if(R!=itv[x].end()) {
        if(R->X-1==y) {
            r = R->Y;
            upd(x,*R,0);
        }
    }
    upd(x,{y,y},0);
    upd(x,{l,r},1);
}
void del(int x,int y) {
    int l,r;
    set<pii>::iterator it;
    it = itv[x].upper_bound({y,m+1});
    --it;
    l = it->X; r = it->Y;
    upd(x,{l,r},0);
    if(l<=y-1) upd(x,{l,y-1},1);
    if(y+1<=r) upd(x,{y+1,r},1);
}
int main() {
    int i,j,x,cnt,bound,ans;
    char c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) {
        for(j=1;j<=m;j++) {
            scanf(" %c",&c);
            p[i][j] = c-'0';
        }
    }
    bound = n;
    for(j=1;j<=m;j++) {
        cnt = 0;
        for(i=n;i>=1;i--) {
            if(p[i][j]==0) {
                if(cnt!=0) bound = min(bound, cnt);
                cnt = 0;
            }
            else cnt++;
            con[cnt].push_back({i,j});
        }
    }
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) add(i,j);
    ans = 0;
    for(x=1;x<=bound;x++) {
//        printf("Fixed row = %d\n",x);
        for(auto t : con[x-1]) del(t.X,t.Y);
//        for(i=1;i<=n;i++) {
//            printf("\t");
//            for(auto t : itv[i]) printf("[%d, %d] ",t.X,t.Y);
//            printf("\n");
//        }
        if(!len.empty()) ans = max(ans, x*(*len.begin()));
//        if(!len.empty()) printf("Minimum = %d\n",*len.begin());
    }
    printf("%d",ans);
}

Compilation message (stderr)

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

• Subtask 1: 21 / 100