oj.uz

Submission #885318

# Submission time Handle Problem Language Result Execution time Memory
885318 2023-12-09T12:56:48 Z alexdd Bomb (IZhO17_bomb) C++17
50 / 100
 1000 ms 55712 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 > 500000000)
    {
        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
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 9 ms 40828 KB Output is correct
4 Correct 9 ms 40796 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 0 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 4696 KB Output is correct
18 Correct 1 ms 4700 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 1 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 2 ms 4952 KB Output is correct
24 Correct 1 ms 4956 KB Output is correct
25 Correct 2 ms 4956 KB Output is correct
26 Correct 2 ms 5072 KB Output is correct
27 Correct 6 ms 10076 KB Output is correct
28 Correct 9 ms 10148 KB Output is correct
29 Correct 47 ms 10724 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 10964 KB Output is correct
33 Correct 124 ms 13400 KB Output is correct
34 Correct 9 ms 10332 KB Output is correct
35 Correct 68 ms 13388 KB Output is correct
36 Correct 31 ms 13404 KB Output is correct
37 Correct 1 ms 4952 KB Output is correct
38 Correct 233 ms 30880 KB Output is correct
39 Correct 1 ms 4696 KB Output is correct
40 Execution timed out 1089 ms 22180 KB Time limit exceeded
41 Correct 1 ms 4700 KB Output is correct
42 Correct 3 ms 5068 KB Output is correct
43 Correct 222 ms 31060 KB Output is correct
44 Correct 174 ms 13404 KB Output is correct
45 Incorrect 219 ms 31060 KB Output isn't correct
46 Correct 823 ms 55624 KB Output is correct
47 Incorrect 217 ms 30964 KB Output isn't correct
48 Incorrect 236 ms 31064 KB Output isn't correct
49 Correct 332 ms 55376 KB Output is correct
50 Incorrect 221 ms 31060 KB Output isn't correct
51 Incorrect 228 ms 31060 KB Output isn't correct
52 Incorrect 262 ms 31100 KB Output isn't correct
53 Incorrect 220 ms 31160 KB Output isn't correct
54 Incorrect 221 ms 30880 KB Output isn't correct
55 Incorrect 215 ms 30900 KB Output isn't correct
56 Execution timed out 1041 ms 55712 KB Time limit exceeded
57 Incorrect 217 ms 30912 KB Output isn't correct
58 Incorrect 211 ms 30888 KB Output isn't correct
59 Incorrect 224 ms 30900 KB Output isn't correct
60 Correct 983 ms 55636 KB Output is correct
61 Correct 977 ms 55620 KB Output is correct
62 Correct 233 ms 31112 KB Output is correct
63 Correct 268 ms 31140 KB Output is correct
64 Correct 213 ms 30884 KB Output is correct
65 Execution timed out 1067 ms 55380 KB Time limit exceeded
66 Incorrect 217 ms 30916 KB Output isn't correct
67 Incorrect 215 ms 30900 KB Output isn't correct
68 Incorrect 222 ms 31104 KB Output isn't correct
69 Incorrect 213 ms 31060 KB Output isn't correct
70 Incorrect 140 ms 26536 KB Output isn't correct
71 Incorrect 212 ms 30896 KB Output isn't correct
72 Incorrect 212 ms 31060 KB Output isn't correct
73 Incorrect 215 ms 30892 KB Output isn't correct
74 Incorrect 220 ms 30904 KB Output isn't correct
75 Incorrect 214 ms 30896 KB Output isn't correct
76 Incorrect 220 ms 31068 KB Output isn't correct
77 Incorrect 213 ms 30892 KB Output isn't correct
78 Incorrect 211 ms 31024 KB Output isn't correct
79 Execution timed out 1075 ms 55420 KB Time limit exceeded
80 Execution timed out 1060 ms 55380 KB Time limit exceeded
81 Incorrect 219 ms 30884 KB Output isn't correct
82 Incorrect 232 ms 30888 KB Output isn't correct
83 Incorrect 225 ms 30916 KB Output isn't correct
84 Incorrect 215 ms 30892 KB Output isn't correct
85 Incorrect 235 ms 30884 KB Output isn't correct
86 Execution timed out 1076 ms 55456 KB Time limit exceeded
87 Incorrect 213 ms 30904 KB Output isn't correct
88 Incorrect 229 ms 30896 KB Output isn't correct
89 Incorrect 223 ms 30900 KB Output isn't correct
90 Incorrect 180 ms 26540 KB Output isn't correct
91 Incorrect 243 ms 30908 KB Output isn't correct
92 Incorrect 219 ms 31140 KB Output isn't correct
93 Execution timed out 1068 ms 55468 KB Time limit exceeded
94 Incorrect 228 ms 30884 KB Output isn't correct
95 Incorrect 215 ms 30908 KB Output isn't correct
96 Incorrect 230 ms 30892 KB Output isn't correct
97 Execution timed out 1047 ms 55612 KB Time limit exceeded
98 Incorrect 215 ms 30900 KB Output isn't correct
99 Incorrect 222 ms 30884 KB Output isn't correct
100 Execution timed out 1069 ms 55468 KB Time limit exceeded