oj.uz

Submission #885316

# Submission time Handle Problem Language Result Execution time Memory
885316 2023-12-09T12:56:07 Z alexdd Bomb (IZhO17_bomb) C++17
51 / 100
 330 ms 55616 KB 
#include<iostream>
using namespace std;
int n,m;
char mat[2505][2505];
int sump[2505][2505];
int mars[2505][2505];
bool verif(int cntx, int cnty)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            mars[i][j]=0;
    for(int i=1;i+cntx-1<=n;i++)
    {
        for(int j=1;j+cnty-1<=m;j++)
        {
            if(sump[i+cntx-1][j+cnty-1] - sump[i+cntx-1][j-1] - sump[i-1][j+cnty-1] + sump[i-1][j-1] == cntx*cnty)///toate is 1
            {
                mars[i][j]++;
                mars[i][j+cnty]--;
                mars[i+cntx][j]--;
                mars[i+cntx][j+cnty]++;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            mars[i][j] += mars[i-1][j] + mars[i][j-1] - mars[i-1][j-1];
            if(mars[i][j]==0 && mat[i][j]=='1')
                return 0;
        }
    }
    return 1;
}
signed main()
{
    cin>>n>>m;
    int minx=n,miny=m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>mat[i][j];
            sump[i][j] = sump[i-1][j] + sump[i][j-1] - sump[i-1][j-1];
            if(mat[i][j]=='1')
                sump[i][j]++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(mat[i][j]=='1' && (j==m || mat[i][j+1]=='0'))
            {
                int cnt=0;
                for(int u=j;u>0;u--)
                {
                    if(mat[i][u]=='0')
                        break;
                    cnt++;
                }
                miny = min(miny, cnt);
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(mat[j][i]=='1' && (j==n || mat[j+1][i]=='0'))
            {
                int cnt=0;
                for(int u=j;u>0;u--)
                {
                    if(mat[u][i]=='0')
                        break;
                    cnt++;
                }
                minx = min(minx, cnt);
            }
        }
    }
    if(1LL*miny * n * m > 100000000)
    {
        cout<<minx*miny;
        return 0;
    }
    //minx=n;miny=m;
    int poz=0, mxm=0;
    for(int i=minx;i>0;i--)
    {
        if(i*miny <= mxm)
            break;
        while(poz+1<=miny && verif(i,poz+1))
        {
            poz++;
        }
        mxm = max(mxm, i*poz);
    }
    cout<<mxm;
    return 0;
}

Subtask #1
51.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 9 ms 40940 KB Output is correct
4 Correct 9 ms 41020 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 4700 KB Output is correct
17 Correct 1 ms 4700 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct
21 Correct 1 ms 4700 KB Output is correct
22 Correct 1 ms 4952 KB Output is correct
23 Correct 2 ms 4956 KB Output is correct
24 Correct 1 ms 4972 KB Output is correct
25 Correct 2 ms 4956 KB Output is correct
26 Correct 2 ms 4956 KB Output is correct
27 Correct 6 ms 10076 KB Output is correct
28 Correct 9 ms 10108 KB Output is correct
29 Correct 47 ms 10588 KB Output is correct
30 Correct 47 ms 11100 KB Output is correct
31 Correct 33 ms 10588 KB Output is correct
32 Correct 41 ms 10844 KB Output is correct
33 Correct 125 ms 13404 KB Output is correct
34 Correct 8 ms 10332 KB Output is correct
35 Correct 60 ms 13404 KB Output is correct
36 Correct 30 ms 13400 KB Output is correct
37 Correct 1 ms 4700 KB Output is correct
38 Correct 231 ms 31200 KB Output is correct
39 Correct 1 ms 4700 KB Output is correct
40 Incorrect 29 ms 11860 KB Output isn't correct
41 Correct 1 ms 4700 KB Output is correct
42 Correct 3 ms 4956 KB Output is correct
43 Correct 218 ms 31068 KB Output is correct
44 Correct 176 ms 13404 KB Output is correct
45 Incorrect 217 ms 30908 KB Output isn't correct
46 Correct 222 ms 31056 KB Output is correct
47 Incorrect 227 ms 31096 KB Output isn't correct
48 Incorrect 220 ms 31056 KB Output isn't correct
49 Correct 330 ms 55616 KB Output is correct
50 Incorrect 217 ms 31060 KB Output isn't correct
51 Incorrect 217 ms 30884 KB Output isn't correct
52 Incorrect 222 ms 31168 KB Output isn't correct
53 Incorrect 215 ms 31060 KB Output isn't correct
54 Incorrect 213 ms 30892 KB Output isn't correct
55 Incorrect 212 ms 31056 KB Output isn't correct
56 Correct 225 ms 30892 KB Output is correct
57 Incorrect 211 ms 31064 KB Output isn't correct
58 Incorrect 219 ms 31264 KB Output isn't correct
59 Incorrect 242 ms 31056 KB Output isn't correct
60 Correct 216 ms 31056 KB Output is correct
61 Correct 252 ms 31144 KB Output is correct
62 Correct 226 ms 31060 KB Output is correct
63 Correct 242 ms 31056 KB Output is correct
64 Correct 246 ms 30956 KB Output is correct
65 Incorrect 220 ms 30908 KB Output isn't correct
66 Incorrect 224 ms 31292 KB Output isn't correct
67 Incorrect 219 ms 31060 KB Output isn't correct
68 Incorrect 226 ms 31056 KB Output isn't correct
69 Incorrect 220 ms 31136 KB Output isn't correct
70 Incorrect 135 ms 26448 KB Output isn't correct
71 Incorrect 249 ms 31020 KB Output isn't correct
72 Incorrect 215 ms 31012 KB Output isn't correct
73 Incorrect 211 ms 31096 KB Output isn't correct
74 Incorrect 213 ms 30868 KB Output isn't correct
75 Incorrect 235 ms 30996 KB Output isn't correct
76 Incorrect 215 ms 31060 KB Output isn't correct
77 Incorrect 212 ms 31044 KB Output isn't correct
78 Incorrect 234 ms 31156 KB Output isn't correct
79 Incorrect 211 ms 31056 KB Output isn't correct
80 Incorrect 207 ms 30892 KB Output isn't correct
81 Incorrect 216 ms 30896 KB Output isn't correct
82 Incorrect 212 ms 30884 KB Output isn't correct
83 Incorrect 212 ms 30908 KB Output isn't correct
84 Incorrect 211 ms 31064 KB Output isn't correct
85 Incorrect 226 ms 30896 KB Output isn't correct
86 Incorrect 218 ms 31056 KB Output isn't correct
87 Incorrect 218 ms 30912 KB Output isn't correct
88 Incorrect 225 ms 31056 KB Output isn't correct
89 Incorrect 215 ms 30896 KB Output isn't correct
90 Incorrect 137 ms 26536 KB Output isn't correct
91 Incorrect 213 ms 30904 KB Output isn't correct
92 Incorrect 232 ms 31060 KB Output isn't correct
93 Incorrect 218 ms 30976 KB Output isn't correct
94 Incorrect 230 ms 30896 KB Output isn't correct
95 Incorrect 212 ms 30888 KB Output isn't correct
96 Incorrect 227 ms 30888 KB Output isn't correct
97 Incorrect 219 ms 31052 KB Output isn't correct
98 Incorrect 235 ms 31268 KB Output isn't correct
99 Incorrect 214 ms 31056 KB Output isn't correct
100 Incorrect 219 ms 31100 KB Output isn't correct