oj.uz

Submission #885319

# Submission time Handle Problem Language Result Execution time Memory
885319 2023-12-09T12:57:09 Z alexdd Bomb (IZhO17_bomb) C++17
51 / 100
 1000 ms 55720 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 > 300000000)
    {
        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 4700 KB Output is correct
3 Correct 8 ms 40816 KB Output is correct
4 Correct 9 ms 40800 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 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 4696 KB Output is correct
17 Correct 2 ms 4700 KB Output is correct
18 Correct 2 ms 4700 KB Output is correct
19 Correct 2 ms 4952 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 4956 KB Output is correct
23 Correct 3 ms 4956 KB Output is correct
24 Correct 2 ms 4956 KB Output is correct
25 Correct 3 ms 4956 KB Output is correct
26 Correct 2 ms 4956 KB Output is correct
27 Correct 6 ms 10180 KB Output is correct
28 Correct 8 ms 10332 KB Output is correct
29 Correct 48 ms 10764 KB Output is correct
30 Correct 50 ms 11200 KB Output is correct
31 Correct 33 ms 10584 KB Output is correct
32 Correct 43 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 70 ms 13404 KB Output is correct
36 Correct 30 ms 13400 KB Output is correct
37 Correct 1 ms 4912 KB Output is correct
38 Correct 247 ms 30884 KB Output is correct
39 Correct 1 ms 4696 KB Output is correct
40 Execution timed out 1089 ms 22184 KB Time limit exceeded
41 Correct 1 ms 4696 KB Output is correct
42 Correct 3 ms 4956 KB Output is correct
43 Correct 220 ms 30900 KB Output is correct
44 Correct 190 ms 13272 KB Output is correct
45 Incorrect 229 ms 31060 KB Output isn't correct
46 Correct 859 ms 55720 KB Output is correct
47 Incorrect 221 ms 30888 KB Output isn't correct
48 Incorrect 221 ms 30904 KB Output isn't correct
49 Correct 336 ms 55464 KB Output is correct
50 Incorrect 228 ms 30904 KB Output isn't correct
51 Incorrect 217 ms 30932 KB Output isn't correct
52 Incorrect 215 ms 30884 KB Output isn't correct
53 Incorrect 223 ms 30888 KB Output isn't correct
54 Incorrect 212 ms 30888 KB Output isn't correct
55 Incorrect 214 ms 30888 KB Output isn't correct
56 Correct 226 ms 31084 KB Output is correct
57 Incorrect 213 ms 30896 KB Output isn't correct
58 Incorrect 219 ms 31056 KB Output isn't correct
59 Incorrect 216 ms 30900 KB Output isn't correct
60 Correct 983 ms 55616 KB Output is correct
61 Correct 980 ms 55632 KB Output is correct
62 Correct 218 ms 31060 KB Output is correct
63 Correct 270 ms 30908 KB Output is correct
64 Correct 227 ms 31056 KB Output is correct
65 Incorrect 222 ms 30888 KB Output isn't correct
66 Incorrect 225 ms 30884 KB Output isn't correct
67 Incorrect 217 ms 31056 KB Output isn't correct
68 Incorrect 240 ms 31168 KB Output isn't correct
69 Incorrect 212 ms 31060 KB Output isn't correct
70 Incorrect 135 ms 26448 KB Output isn't correct
71 Incorrect 214 ms 31164 KB Output isn't correct
72 Incorrect 210 ms 31060 KB Output isn't correct
73 Incorrect 212 ms 30896 KB Output isn't correct
74 Incorrect 211 ms 31156 KB Output isn't correct
75 Incorrect 209 ms 30964 KB Output isn't correct
76 Incorrect 211 ms 31052 KB Output isn't correct
77 Incorrect 215 ms 30888 KB Output isn't correct
78 Incorrect 237 ms 30896 KB Output isn't correct
79 Execution timed out 1067 ms 55468 KB Time limit exceeded
80 Execution timed out 1065 ms 55468 KB Time limit exceeded
81 Incorrect 211 ms 30888 KB Output isn't correct
82 Incorrect 256 ms 31056 KB Output isn't correct
83 Incorrect 218 ms 31312 KB Output isn't correct
84 Incorrect 208 ms 30916 KB Output isn't correct
85 Incorrect 211 ms 31060 KB Output isn't correct
86 Incorrect 222 ms 31076 KB Output isn't correct
87 Incorrect 216 ms 31060 KB Output isn't correct
88 Incorrect 225 ms 30896 KB Output isn't correct
89 Incorrect 240 ms 31064 KB Output isn't correct
90 Incorrect 138 ms 26452 KB Output isn't correct
91 Incorrect 220 ms 31092 KB Output isn't correct
92 Incorrect 237 ms 31080 KB Output isn't correct
93 Incorrect 232 ms 31012 KB Output isn't correct
94 Incorrect 237 ms 30900 KB Output isn't correct
95 Incorrect 223 ms 31028 KB Output isn't correct
96 Incorrect 215 ms 30888 KB Output isn't correct
97 Incorrect 226 ms 30896 KB Output isn't correct
98 Incorrect 234 ms 30888 KB Output isn't correct
99 Incorrect 218 ms 30888 KB Output isn't correct
100 Incorrect 222 ms 30888 KB Output isn't correct