답안 #885632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
885632	2023-12-10T10:36:32 Z	alexdd	Bomb (IZhO17_bomb)	C++17	70 / 100	1000 ms	62292 KB

bomb

#include<iostream>
using namespace std;
int n,m;
char mat[2505][2505];
int sump[2505][2505];
int mars[2505][2505];
int pver[2505][2505];
bool verif(int cntx, int cnty)
{
    if(pver[cntx][cnty]!=0)
    {
        if(pver[cntx][cnty]==-1)
            return 0;
        else
            return 1;
    }
    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')
            {
                pver[cntx][cnty]=-1;
                return 0;
            }
        }
    }
    pver[cntx][cnty]=1;
    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;
        poz = max(poz, (mxm-1)/i+1);
        while(poz+1<=miny && verif(i,poz+1))
        {
            poz++;
        }
        if(verif(i,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;
        poz = max(poz, (mxm-1)/i+1);
        while(poz+1<=minx && verif(poz+1,i))
        {
            poz++;
        }
        if(verif(poz,i)) mxm = max(mxm, i*poz);
    }
    cout<<mxm;
}
void solve_bulaneala(int minx, int miny)
{
    int mxm=0,prec=1,cntnm=0;
    for(int i=miny;i>0;i--)
    {
        if(i*minx <= mxm)
            break;
        int st,dr,mij,ans=0;
        st=max(prec, (mxm-1)/i+1);
        dr=minx;
        if(!verif(st,i))
            continue;
        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);
        cntnm++;
        if(cntnm>=3)
            break;
        prec=ans;
    }
    prec=1;
    cntnm=0;
    for(int i=minx;i>0;i--)
    {
        if(i*miny <= mxm)
            break;
        int st,dr,mij,ans=0;
        st=max(prec, (mxm-1)/i+1);
        dr=miny;
        if(!verif(i,st))
            continue;
        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);
        cntnm++;
        if(cntnm>=3)
            break;
        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

70.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4440 KB	Output is correct
3	Correct	9 ms	42916 KB	Output is correct
4	Correct	8 ms	42840 KB	Output is correct
5	Correct	2 ms	4440 KB	Output is correct
6	Correct	1 ms	4536 KB	Output is correct
7	Correct	1 ms	4444 KB	Output is correct
8	Correct	1 ms	4444 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	4444 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	4444 KB	Output is correct
13	Correct	1 ms	4444 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	4696 KB	Output is correct
16	Correct	1 ms	4444 KB	Output is correct
17	Correct	2 ms	6744 KB	Output is correct
18	Correct	1 ms	6748 KB	Output is correct
19	Correct	2 ms	6844 KB	Output is correct
20	Correct	2 ms	7004 KB	Output is correct
21	Correct	2 ms	6748 KB	Output is correct
22	Correct	1 ms	6752 KB	Output is correct
23	Correct	2 ms	7000 KB	Output is correct
24	Correct	2 ms	7004 KB	Output is correct
25	Correct	2 ms	7004 KB	Output is correct
26	Correct	2 ms	7000 KB	Output is correct
27	Correct	6 ms	12124 KB	Output is correct
28	Correct	7 ms	12380 KB	Output is correct
29	Incorrect	29 ms	12888 KB	Output isn't correct
30	Correct	46 ms	13704 KB	Output is correct
31	Correct	34 ms	12892 KB	Output is correct
32	Correct	40 ms	13400 KB	Output is correct
33	Correct	110 ms	15956 KB	Output is correct
34	Correct	7 ms	12376 KB	Output is correct
35	Correct	46 ms	15452 KB	Output is correct
36	Correct	25 ms	15452 KB	Output is correct
37	Correct	1 ms	4444 KB	Output is correct
38	Correct	243 ms	61148 KB	Output is correct
39	Correct	1 ms	4440 KB	Output is correct
40	Correct	189 ms	24852 KB	Output is correct
41	Correct	1 ms	4640 KB	Output is correct
42	Correct	4 ms	7004 KB	Output is correct
43	Correct	387 ms	61284 KB	Output is correct
44	Correct	83 ms	16212 KB	Output is correct
45	Incorrect	585 ms	61280 KB	Output isn't correct
46	Correct	719 ms	61012 KB	Output is correct
47	Incorrect	666 ms	61460 KB	Output isn't correct
48	Correct	535 ms	61200 KB	Output is correct
49	Correct	284 ms	61008 KB	Output is correct
50	Correct	489 ms	61300 KB	Output is correct
51	Correct	514 ms	61524 KB	Output is correct
52	Correct	491 ms	61260 KB	Output is correct
53	Correct	506 ms	61556 KB	Output is correct
54	Correct	715 ms	61296 KB	Output is correct
55	Correct	736 ms	61528 KB	Output is correct
56	Correct	306 ms	61232 KB	Output is correct
57	Correct	696 ms	61524 KB	Output is correct
58	Correct	811 ms	61540 KB	Output is correct
59	Correct	825 ms	61336 KB	Output is correct
60	Correct	347 ms	61268 KB	Output is correct
61	Correct	605 ms	61264 KB	Output is correct
62	Correct	392 ms	61256 KB	Output is correct
63	Correct	323 ms	61280 KB	Output is correct
64	Correct	378 ms	61268 KB	Output is correct
65	Correct	593 ms	61260 KB	Output is correct
66	Correct	393 ms	61264 KB	Output is correct
67	Correct	469 ms	61292 KB	Output is correct
68	Correct	471 ms	61140 KB	Output is correct
69	Correct	635 ms	61488 KB	Output is correct
70	Execution timed out	1046 ms	52820 KB	Time limit exceeded
71	Execution timed out	1067 ms	61564 KB	Time limit exceeded
72	Execution timed out	1096 ms	61252 KB	Time limit exceeded
73	Execution timed out	1062 ms	61280 KB	Time limit exceeded
74	Execution timed out	1067 ms	61476 KB	Time limit exceeded
75	Execution timed out	1047 ms	61268 KB	Time limit exceeded
76	Execution timed out	1052 ms	61544 KB	Time limit exceeded
77	Execution timed out	1065 ms	61280 KB	Time limit exceeded
78	Execution timed out	1033 ms	61284 KB	Time limit exceeded
79	Execution timed out	1050 ms	62292 KB	Time limit exceeded
80	Execution timed out	1044 ms	61636 KB	Time limit exceeded
81	Execution timed out	1035 ms	61260 KB	Time limit exceeded
82	Execution timed out	1055 ms	61464 KB	Time limit exceeded
83	Execution timed out	1052 ms	61276 KB	Time limit exceeded
84	Execution timed out	1028 ms	61508 KB	Time limit exceeded
85	Execution timed out	1029 ms	61280 KB	Time limit exceeded
86	Correct	465 ms	61292 KB	Output is correct
87	Execution timed out	1096 ms	61260 KB	Time limit exceeded
88	Execution timed out	1052 ms	61520 KB	Time limit exceeded
89	Execution timed out	1048 ms	61680 KB	Time limit exceeded
90	Execution timed out	1062 ms	52564 KB	Time limit exceeded
91	Execution timed out	1064 ms	61180 KB	Time limit exceeded
92	Execution timed out	1065 ms	61788 KB	Time limit exceeded
93	Correct	568 ms	61264 KB	Output is correct
94	Execution timed out	1043 ms	61252 KB	Time limit exceeded
95	Execution timed out	1050 ms	61284 KB	Time limit exceeded
96	Execution timed out	1065 ms	61524 KB	Time limit exceeded
97	Correct	512 ms	61272 KB	Output is correct
98	Execution timed out	1070 ms	61288 KB	Time limit exceeded
99	Execution timed out	1016 ms	61280 KB	Time limit exceeded
100	Correct	619 ms	61748 KB	Output is correct