Submission #366562

#	Time	Username	Problem	Language	Result	Execution time	Memory
366562		nicolaalexandra	Bomb (IZhO17_bomb)	C++14	13 / 100	1107 ms	131076 KiB

bomb

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

int n,m,i,j;
char s[DIM];
int dp_up[DIM][DIM],St[DIM],Dr[DIM],v[DIM][DIM],a[DIM][DIM];
deque <int> d;

struct event{
    int x,y,x2,y2,val;
};
vector <event> events;

inline int cmp (event a, event b){
    return a.val < b.val;
}

int verif (int poz){

    memset (v,0,sizeof v);
    int ok = 0;
    for (int i=poz;i<events.size();i++){
        int x = events[i].x, x2 = events[i].x2, y = events[i].y, y2 = events[i].y2;

        if (x <= 3 && 3 <= x2 && y <= 6 && 6 <= y2)
            ok = 1;

        v[x][y]++;
        v[x][y2+1]--;
        v[x2+1][y]--;
        v[x2+1][y2+1]++;
    }

    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            v[i][j] += v[i-1][j] + v[i][j-1] - v[i-1][j-1];
            if (!v[i][j] && a[i][j])
                return 0;
        }

    return 1;
}

int main (){

    //ifstream cin ("bomb.in");
    //ofstream cout ("bomb.out");

    cin>>n>>m;
    for (i=1;i<=n;i++){
        cin>>s+1;
        for (j=1;j<=m;j++)
            a[i][j] = s[j] - '0';
    }

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (a[i][j])
                dp_up[i][j] = 1 + dp_up[i-1][j];

    for (i=1;i<=n;i++){
        memset (St,0,sizeof St);
        memset (Dr,0,sizeof Dr);
        d.clear();
        int last = 0;
        for (j=1;j<=m;j++){
            if (!dp_up[i][j]){
                d.clear();
                last = j;
            }

            while (!d.empty() && dp_up[i][j] <= dp_up[i][d.back()])
                d.pop_back();

            if (d.empty())
                St[j] = last;
            else St[j] = d.back();

            d.push_back(j);
        }


        d.clear(), last = m+1;

        for (j=m;j;j--){
            if (!dp_up[i][j]){
                d.clear();
                last = j;
            }

            while (!d.empty() && dp_up[i][j] <= dp_up[i][d.back()])
                d.pop_back();

            if (d.empty())
                Dr[j] = last;
            else Dr[j] = d.back();

            d.push_back(j);
        }

        for (j=1;j<=m;j++){
            if (!dp_up[i][j])
                continue;

            int x = i - dp_up[i][j] + 1, x2 = i;
            int y = St[j] + 1, y2 = Dr[j] - 1;

            if (x == 1 && x2 == 3 && y == 1 && y2 == 6)
                x = 1;

            events.push_back({x,y,x2,y2,dp_up[i][j] * (Dr[j] - St[j] - 1)});
        }
    }

    sort (events.begin(),events.end(),cmp);

    int st = 0, dr = events.size()-1, sol = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif(mid)){
            sol = events[mid].val;
            st = mid+1;
        } else dr = mid-1;
    }

    cout<<sol;

    return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'int verif(int)':
bomb.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i=poz;i<events.size();i++){
      |                    ~^~~~~~~~~~~~~~
bomb.cpp:22:9: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   22 |     int ok = 0;
      |         ^~
bomb.cpp: In function 'int main()':
bomb.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         cin>>s+1;
      |              ~^~

• Subtask 1: 13 / 100