답안 #885622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
885622	2023-12-10T10:26:15 Z	alexdd	Bomb (IZhO17_bomb)	C++17	68 / 100	1000 ms	61200 KB

bomb

#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--)
    {
        if(i*minx <= mxm)
            break;
        int st,dr,mij,ans=0;
        st=max(prec, (mxm-1)/i+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--)
    {
        if(i*miny <= mxm)
            break;
        int st,dr,mij,ans=0;
        st=max(prec, (mxm-1)/i+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;
}

Subtask #1

68.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	4700 KB	Output is correct
3	Correct	8 ms	40796 KB	Output is correct
4	Correct	8 ms	40896 KB	Output is correct
5	Correct	1 ms	2492 KB	Output is correct
6	Correct	1 ms	2648 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	4540 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	1 ms	4696 KB	Output is correct
12	Correct	1 ms	2396 KB	Output is correct
13	Correct	1 ms	2488 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	1 ms	5040 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	4956 KB	Output is correct
24	Correct	2 ms	4956 KB	Output is correct
25	Correct	2 ms	5088 KB	Output is correct
26	Correct	2 ms	4956 KB	Output is correct
27	Correct	6 ms	11868 KB	Output is correct
28	Correct	8 ms	12124 KB	Output is correct
29	Incorrect	31 ms	12124 KB	Output isn't correct
30	Correct	32 ms	12124 KB	Output is correct
31	Correct	24 ms	12288 KB	Output is correct
32	Correct	29 ms	12120 KB	Output is correct
33	Correct	89 ms	14428 KB	Output is correct
34	Correct	8 ms	10328 KB	Output is correct
35	Correct	49 ms	14452 KB	Output is correct
36	Correct	25 ms	14428 KB	Output is correct
37	Correct	1 ms	4540 KB	Output is correct
38	Correct	243 ms	60648 KB	Output is correct
39	Correct	1 ms	4696 KB	Output is correct
40	Correct	73 ms	22640 KB	Output is correct
41	Correct	1 ms	4696 KB	Output is correct
42	Correct	2 ms	4960 KB	Output is correct
43	Correct	362 ms	60504 KB	Output is correct
44	Correct	99 ms	14300 KB	Output is correct
45	Incorrect	646 ms	60936 KB	Output isn't correct
46	Correct	741 ms	60744 KB	Output is correct
47	Incorrect	588 ms	60732 KB	Output isn't correct
48	Correct	574 ms	60500 KB	Output is correct
49	Correct	312 ms	60620 KB	Output is correct
50	Correct	548 ms	60736 KB	Output is correct
51	Correct	548 ms	60752 KB	Output is correct
52	Correct	574 ms	60736 KB	Output is correct
53	Correct	555 ms	60752 KB	Output is correct
54	Correct	754 ms	60728 KB	Output is correct
55	Correct	762 ms	60736 KB	Output is correct
56	Correct	267 ms	60568 KB	Output is correct
57	Correct	815 ms	60752 KB	Output is correct
58	Correct	911 ms	60760 KB	Output is correct
59	Correct	856 ms	60728 KB	Output is correct
60	Correct	326 ms	60504 KB	Output is correct
61	Correct	636 ms	60560 KB	Output is correct
62	Correct	371 ms	60692 KB	Output is correct
63	Correct	305 ms	60740 KB	Output is correct
64	Correct	362 ms	60948 KB	Output is correct
65	Correct	523 ms	60620 KB	Output is correct
66	Correct	393 ms	60984 KB	Output is correct
67	Correct	513 ms	60616 KB	Output is correct
68	Correct	513 ms	60496 KB	Output is correct
69	Correct	787 ms	60752 KB	Output is correct
70	Incorrect	308 ms	52096 KB	Output isn't correct
71	Incorrect	705 ms	60500 KB	Output isn't correct
72	Incorrect	697 ms	60840 KB	Output isn't correct
73	Incorrect	621 ms	60496 KB	Output isn't correct
74	Incorrect	749 ms	60780 KB	Output isn't correct
75	Incorrect	724 ms	60672 KB	Output isn't correct
76	Incorrect	766 ms	60728 KB	Output isn't correct
77	Incorrect	802 ms	60736 KB	Output isn't correct
78	Incorrect	826 ms	60856 KB	Output isn't correct
79	Execution timed out	1066 ms	60624 KB	Time limit exceeded
80	Execution timed out	1042 ms	60704 KB	Time limit exceeded
81	Incorrect	462 ms	60736 KB	Output isn't correct
82	Incorrect	800 ms	60960 KB	Output isn't correct
83	Incorrect	851 ms	60572 KB	Output isn't correct
84	Correct	724 ms	60576 KB	Output is correct
85	Incorrect	656 ms	60684 KB	Output isn't correct
86	Incorrect	338 ms	60756 KB	Output isn't correct
87	Correct	573 ms	60496 KB	Output is correct
88	Incorrect	680 ms	60500 KB	Output isn't correct
89	Incorrect	462 ms	60640 KB	Output isn't correct
90	Incorrect	428 ms	52312 KB	Output isn't correct
91	Incorrect	571 ms	60496 KB	Output isn't correct
92	Incorrect	553 ms	60736 KB	Output isn't correct
93	Incorrect	377 ms	60740 KB	Output isn't correct
94	Incorrect	483 ms	60980 KB	Output isn't correct
95	Incorrect	831 ms	60948 KB	Output isn't correct
96	Incorrect	725 ms	60736 KB	Output isn't correct
97	Incorrect	334 ms	61200 KB	Output isn't correct
98	Incorrect	841 ms	60796 KB	Output isn't correct
99	Incorrect	520 ms	60496 KB	Output isn't correct
100	Incorrect	373 ms	60740 KB	Output isn't correct