oj.uz

Submission #885399

# Submission time Handle Problem Language Result Execution time Memory
885399 2023-12-09T15:14:21 Z alexdd Bomb (IZhO17_bomb) C++17
48 / 100
 1000 ms 55864 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]++;
            }
            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;
}
void solve_bulaneala(int minx, int miny)
{
    int mxm=0,prec=1;
    //for(int i=miny;i>max(0,miny-4);i--)
    for(int i=min(miny,3);i>0;i--)
    {
        if(i*minx <= mxm)
            break;
        int st,dr,mij,ans=0;
        st=1;
        dr=minx;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(verif(mij,i))
            {
                ans = max(ans, mij);
                st=mij+1;
            }
            else
            {
                dr=mij-1;
            }
        }
        mxm = max(mxm, i*ans);
        prec=ans;
    }
    prec=1;
    //for(int i=minx;i>max(0,minx-4);i--)
    for(int i=min(minx,3);i>0;i--)
    {
        if(i*miny <= mxm)
            break;
        int st,dr,mij,ans=0;
        st=1;
        dr=miny;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(verif(i,mij))
            {
                ans = max(ans, mij);
                st=mij+1;
            }
            else
            {
                dr=mij-1;
            }
        }
        mxm = max(mxm, i*ans);
        prec=ans;
    }
    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 if(1)
    {
        solve_bulaneala(minx,miny);
        return 0;
    }
    else
    {
        cout<<minx*miny;
        return 0;
    }
    return 0;
}

Compilation message

bomb.cpp: In function 'void solve_bulaneala(int, int)':
bomb.cpp:62:15: warning: variable 'prec' set but not used [-Wunused-but-set-variable]
   62 |     int mxm=0,prec=1;
      |               ^~~~

Subtask #1
48.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 40792 KB Output is correct
4 Correct 10 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 1 ms 2396 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 4700 KB Output is correct
12 Correct 0 ms 2480 KB Output is correct
13 Correct 1 ms 2392 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 4696 KB Output is correct
19 Correct 2 ms 4952 KB Output is correct
20 Correct 1 ms 4956 KB Output is correct
21 Correct 1 ms 4700 KB Output is correct
22 Correct 2 ms 4956 KB Output is correct
23 Correct 2 ms 4956 KB Output is correct
24 Correct 2 ms 4956 KB Output is correct
25 Correct 2 ms 4952 KB Output is correct
26 Correct 2 ms 5208 KB Output is correct
27 Correct 7 ms 11868 KB Output is correct
28 Correct 8 ms 12032 KB Output is correct
29 Incorrect 38 ms 11868 KB Output isn't correct
30 Correct 34 ms 12120 KB Output is correct
31 Correct 24 ms 12124 KB Output is correct
32 Correct 30 ms 12072 KB Output is correct
33 Correct 93 ms 14172 KB Output is correct
34 Correct 7 ms 10492 KB Output is correct
35 Correct 51 ms 14172 KB Output is correct
36 Correct 26 ms 14128 KB Output is correct
37 Correct 1 ms 4700 KB Output is correct
38 Incorrect 278 ms 55544 KB Output isn't correct
39 Correct 1 ms 4704 KB Output is correct
40 Incorrect 67 ms 21760 KB Output isn't correct
41 Correct 1 ms 4712 KB Output is correct
42 Correct 2 ms 4968 KB Output is correct
43 Incorrect 407 ms 55620 KB Output isn't correct
44 Correct 107 ms 14172 KB Output is correct
45 Incorrect 364 ms 55612 KB Output isn't correct
46 Correct 778 ms 55464 KB Output is correct
47 Incorrect 535 ms 55740 KB Output isn't correct
48 Incorrect 511 ms 55616 KB Output isn't correct
49 Correct 307 ms 55616 KB Output is correct
50 Incorrect 518 ms 55624 KB Output isn't correct
51 Incorrect 481 ms 55476 KB Output isn't correct
52 Incorrect 554 ms 55416 KB Output isn't correct
53 Incorrect 495 ms 55380 KB Output isn't correct
54 Incorrect 502 ms 55380 KB Output isn't correct
55 Incorrect 527 ms 55552 KB Output isn't correct
56 Incorrect 331 ms 55464 KB Output isn't correct
57 Incorrect 510 ms 55520 KB Output isn't correct
58 Incorrect 535 ms 55456 KB Output isn't correct
59 Incorrect 501 ms 55468 KB Output isn't correct
60 Incorrect 361 ms 55656 KB Output isn't correct
61 Correct 674 ms 55620 KB Output is correct
62 Incorrect 395 ms 55616 KB Output isn't correct
63 Incorrect 384 ms 55620 KB Output isn't correct
64 Incorrect 434 ms 55616 KB Output isn't correct
65 Incorrect 500 ms 55740 KB Output isn't correct
66 Correct 393 ms 55472 KB Output is correct
67 Incorrect 587 ms 55456 KB Output isn't correct
68 Incorrect 542 ms 55616 KB Output isn't correct
69 Incorrect 563 ms 55380 KB Output isn't correct
70 Incorrect 307 ms 48292 KB Output isn't correct
71 Incorrect 888 ms 55612 KB Output isn't correct
72 Incorrect 679 ms 55608 KB Output isn't correct
73 Incorrect 612 ms 55384 KB Output isn't correct
74 Incorrect 963 ms 55616 KB Output isn't correct
75 Incorrect 779 ms 55608 KB Output isn't correct
76 Execution timed out 1035 ms 55376 KB Time limit exceeded
77 Incorrect 969 ms 55612 KB Output isn't correct
78 Execution timed out 1002 ms 55456 KB Time limit exceeded
79 Execution timed out 1034 ms 55464 KB Time limit exceeded
80 Execution timed out 1036 ms 55628 KB Time limit exceeded
81 Incorrect 688 ms 55376 KB Output isn't correct
82 Incorrect 780 ms 55724 KB Output isn't correct
83 Incorrect 874 ms 55480 KB Output isn't correct
84 Correct 749 ms 55588 KB Output is correct
85 Incorrect 885 ms 55612 KB Output isn't correct
86 Correct 548 ms 55616 KB Output is correct
87 Correct 881 ms 55616 KB Output is correct
88 Incorrect 924 ms 55612 KB Output isn't correct
89 Incorrect 683 ms 55624 KB Output isn't correct
90 Incorrect 564 ms 48452 KB Output isn't correct
91 Incorrect 943 ms 55864 KB Output isn't correct
92 Incorrect 605 ms 55376 KB Output isn't correct
93 Incorrect 540 ms 55496 KB Output isn't correct
94 Incorrect 637 ms 55624 KB Output isn't correct
95 Execution timed out 1028 ms 55632 KB Time limit exceeded
96 Incorrect 914 ms 55608 KB Output isn't correct
97 Incorrect 553 ms 55380 KB Output isn't correct
98 Incorrect 741 ms 55376 KB Output isn't correct
99 Incorrect 999 ms 55624 KB Output isn't correct
100 Correct 675 ms 55468 KB Output is correct