답안 #885629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
885629	2023-12-10T10:32:51 Z	alexdd	Bomb (IZhO17_bomb)	C++17	55 / 100	1000 ms	57980 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;
    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 <= 370000000)
    {
        solve_n3_y(minx,miny);
        return 0;
    }
    else if(1LL*minx*n*m <= 370000000)
    {
        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

55.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	8 ms	42780 KB	Output is correct
4	Correct	8 ms	42820 KB	Output is correct
5	Correct	1 ms	4440 KB	Output is correct
6	Correct	1 ms	4444 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	4444 KB	Output is correct
16	Correct	1 ms	4440 KB	Output is correct
17	Correct	1 ms	6748 KB	Output is correct
18	Correct	1 ms	6748 KB	Output is correct
19	Correct	1 ms	7004 KB	Output is correct
20	Correct	2 ms	7004 KB	Output is correct
21	Correct	1 ms	6748 KB	Output is correct
22	Correct	2 ms	6744 KB	Output is correct
23	Correct	2 ms	7004 KB	Output is correct
24	Correct	1 ms	7004 KB	Output is correct
25	Correct	2 ms	7004 KB	Output is correct
26	Correct	2 ms	7004 KB	Output is correct
27	Correct	5 ms	12120 KB	Output is correct
28	Correct	7 ms	12288 KB	Output is correct
29	Incorrect	29 ms	12820 KB	Output isn't correct
30	Correct	44 ms	13532 KB	Output is correct
31	Correct	31 ms	12892 KB	Output is correct
32	Correct	40 ms	13276 KB	Output is correct
33	Correct	113 ms	15696 KB	Output is correct
34	Correct	6 ms	12380 KB	Output is correct
35	Correct	45 ms	15348 KB	Output is correct
36	Correct	24 ms	15196 KB	Output is correct
37	Correct	1 ms	4444 KB	Output is correct
38	Correct	242 ms	57584 KB	Output is correct
39	Correct	1 ms	4444 KB	Output is correct
40	Correct	569 ms	24368 KB	Output is correct
41	Correct	1 ms	4440 KB	Output is correct
42	Correct	2 ms	7004 KB	Output is correct
43	Correct	362 ms	57316 KB	Output is correct
44	Correct	80 ms	15952 KB	Output is correct
45	Incorrect	645 ms	57568 KB	Output isn't correct
46	Correct	722 ms	57684 KB	Output is correct
47	Incorrect	592 ms	57572 KB	Output isn't correct
48	Execution timed out	1101 ms	57732 KB	Time limit exceeded
49	Correct	281 ms	57320 KB	Output is correct
50	Execution timed out	1054 ms	57580 KB	Time limit exceeded
51	Execution timed out	1055 ms	57788 KB	Time limit exceeded
52	Execution timed out	1045 ms	57424 KB	Time limit exceeded
53	Execution timed out	1034 ms	57340 KB	Time limit exceeded
54	Execution timed out	1065 ms	57684 KB	Time limit exceeded
55	Execution timed out	1032 ms	57424 KB	Time limit exceeded
56	Correct	311 ms	55512 KB	Output is correct
57	Execution timed out	1002 ms	57736 KB	Time limit exceeded
58	Execution timed out	1082 ms	57516 KB	Time limit exceeded
59	Execution timed out	1060 ms	57676 KB	Time limit exceeded
60	Correct	819 ms	57424 KB	Output is correct
61	Correct	792 ms	57428 KB	Output is correct
62	Correct	378 ms	57648 KB	Output is correct
63	Correct	300 ms	57312 KB	Output is correct
64	Correct	365 ms	57684 KB	Output is correct
65	Execution timed out	1069 ms	57444 KB	Time limit exceeded
66	Correct	378 ms	57428 KB	Output is correct
67	Execution timed out	1062 ms	57980 KB	Time limit exceeded
68	Execution timed out	1053 ms	57680 KB	Time limit exceeded
69	Execution timed out	1049 ms	57324 KB	Time limit exceeded
70	Incorrect	303 ms	50484 KB	Output isn't correct
71	Incorrect	703 ms	57684 KB	Output isn't correct
72	Incorrect	675 ms	57684 KB	Output isn't correct
73	Incorrect	591 ms	57428 KB	Output isn't correct
74	Incorrect	724 ms	57320 KB	Output isn't correct
75	Incorrect	704 ms	57508 KB	Output isn't correct
76	Incorrect	756 ms	57572 KB	Output isn't correct
77	Incorrect	774 ms	57664 KB	Output isn't correct
78	Incorrect	791 ms	57728 KB	Output isn't correct
79	Execution timed out	1055 ms	57944 KB	Time limit exceeded
80	Execution timed out	1032 ms	57944 KB	Time limit exceeded
81	Incorrect	464 ms	57464 KB	Output isn't correct
82	Incorrect	785 ms	57572 KB	Output isn't correct
83	Incorrect	840 ms	57836 KB	Output isn't correct
84	Execution timed out	1040 ms	57436 KB	Time limit exceeded
85	Incorrect	657 ms	57576 KB	Output isn't correct
86	Correct	566 ms	57448 KB	Output is correct
87	Correct	588 ms	57512 KB	Output is correct
88	Incorrect	671 ms	57572 KB	Output isn't correct
89	Incorrect	452 ms	57428 KB	Output isn't correct
90	Incorrect	416 ms	50256 KB	Output isn't correct
91	Incorrect	561 ms	57504 KB	Output isn't correct
92	Incorrect	541 ms	57684 KB	Output isn't correct
93	Incorrect	365 ms	57688 KB	Output isn't correct
94	Incorrect	486 ms	57680 KB	Output isn't correct
95	Incorrect	852 ms	57592 KB	Output isn't correct
96	Incorrect	737 ms	57320 KB	Output isn't correct
97	Correct	625 ms	57428 KB	Output is correct
98	Incorrect	868 ms	57532 KB	Output isn't correct
99	Incorrect	540 ms	57564 KB	Output isn't correct
100	Incorrect	403 ms	57428 KB	Output isn't correct