oj.uz

Submission #885323

# Submission time Handle Problem Language Result Execution time Memory
885323 2023-12-09T13:03:29 Z alexdd Bomb (IZhO17_bomb) C++17
52 / 100
 1000 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;
}
void solve_n3_y(int minx, int miny)
{
    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;
}
void solve_n3_x(int minx, int miny)
{
    int poz=0, mxm=0;
    for(int i=miny;i>0;i--)
    {
        if(i*minx <= mxm)
            break;
        while(poz+1<=minx && verif(poz+1,i))
        {
            poz++;
        }
        mxm = max(mxm, i*poz);
    }
    cout<<mxm;
}
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 <= 170000000)
    {
        solve_n3_y(minx,miny);
        return 0;
    }
    else if(1LL*minx*n*m <= 170000000)
    {
        solve_n3_x(minx,miny);
        return 0;
    }
    else
    {
        cout<<minx*miny;
        return 0;
    }
    return 0;
}

Subtask #1
52.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 12 ms 40796 KB Output is correct
4 Correct 8 ms 40796 KB Output is correct
5 Correct 1 ms 2392 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 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 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 4956 KB Output is correct
23 Correct 2 ms 4956 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 4956 KB Output is correct
27 Correct 6 ms 11868 KB Output is correct
28 Correct 11 ms 12056 KB Output is correct
29 Correct 51 ms 11868 KB Output is correct
30 Correct 46 ms 12124 KB Output is correct
31 Correct 34 ms 12124 KB Output is correct
32 Correct 41 ms 12060 KB Output is correct
33 Correct 127 ms 14168 KB Output is correct
34 Correct 8 ms 10332 KB Output is correct
35 Correct 60 ms 14228 KB Output is correct
36 Correct 30 ms 14172 KB Output is correct
37 Correct 1 ms 4700 KB Output is correct
38 Correct 217 ms 30892 KB Output is correct
39 Correct 1 ms 4700 KB Output is correct
40 Incorrect 31 ms 11548 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 224 ms 30884 KB Output is correct
44 Correct 175 ms 14168 KB Output is correct
45 Incorrect 216 ms 30892 KB Output isn't correct
46 Correct 870 ms 55616 KB Output is correct
47 Incorrect 218 ms 31100 KB Output isn't correct
48 Incorrect 219 ms 30912 KB Output isn't correct
49 Correct 336 ms 55484 KB Output is correct
50 Incorrect 238 ms 31044 KB Output isn't correct
51 Incorrect 223 ms 30888 KB Output isn't correct
52 Incorrect 231 ms 31072 KB Output isn't correct
53 Incorrect 220 ms 31060 KB Output isn't correct
54 Incorrect 216 ms 30884 KB Output isn't correct
55 Incorrect 224 ms 30888 KB Output isn't correct
56 Correct 227 ms 30884 KB Output is correct
57 Incorrect 243 ms 31208 KB Output isn't correct
58 Incorrect 214 ms 30884 KB Output isn't correct
59 Incorrect 217 ms 31060 KB Output isn't correct
60 Correct 215 ms 30884 KB Output is correct
61 Correct 742 ms 55376 KB Output is correct
62 Correct 227 ms 31028 KB Output is correct
63 Correct 221 ms 30900 KB Output is correct
64 Correct 213 ms 31056 KB Output is correct
65 Incorrect 238 ms 31288 KB Output isn't correct
66 Correct 537 ms 55464 KB Output is correct
67 Incorrect 261 ms 30880 KB Output isn't correct
68 Incorrect 215 ms 30884 KB Output isn't correct
69 Incorrect 229 ms 30888 KB Output isn't correct
70 Incorrect 137 ms 27732 KB Output isn't correct
71 Incorrect 211 ms 30888 KB Output isn't correct
72 Incorrect 223 ms 31060 KB Output isn't correct
73 Incorrect 217 ms 31160 KB Output isn't correct
74 Incorrect 218 ms 30880 KB Output isn't correct
75 Incorrect 219 ms 31060 KB Output isn't correct
76 Incorrect 211 ms 31056 KB Output isn't correct
77 Incorrect 211 ms 30884 KB Output isn't correct
78 Incorrect 218 ms 31320 KB Output isn't correct
79 Execution timed out 1033 ms 55376 KB Time limit exceeded
80 Execution timed out 1070 ms 55452 KB Time limit exceeded
81 Incorrect 214 ms 31060 KB Output isn't correct
82 Incorrect 213 ms 31132 KB Output isn't correct
83 Incorrect 214 ms 30912 KB Output isn't correct
84 Execution timed out 1070 ms 55420 KB Time limit exceeded
85 Incorrect 216 ms 30940 KB Output isn't correct
86 Incorrect 245 ms 30908 KB Output isn't correct
87 Incorrect 216 ms 30884 KB Output isn't correct
88 Incorrect 215 ms 30896 KB Output isn't correct
89 Incorrect 221 ms 31056 KB Output isn't correct
90 Incorrect 143 ms 27716 KB Output isn't correct
91 Incorrect 229 ms 30896 KB Output isn't correct
92 Incorrect 227 ms 31060 KB Output isn't correct
93 Incorrect 251 ms 30880 KB Output isn't correct
94 Incorrect 215 ms 31060 KB Output isn't correct
95 Incorrect 211 ms 31060 KB Output isn't correct
96 Incorrect 215 ms 31056 KB Output isn't correct
97 Incorrect 231 ms 31112 KB Output isn't correct
98 Incorrect 222 ms 31060 KB Output isn't correct
99 Incorrect 215 ms 31076 KB Output isn't correct
100 Incorrect 234 ms 31148 KB Output isn't correct