답안 #170972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
170972	2019-12-26T20:29:38 Z	davitmarg	Bomb (IZhO17_bomb)	C++17	70 / 100	1000 ms	78300 KB

bomb

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 2505;

int n, m, a[N][N], pr[N][N], nxt[N][N], d[N], Y, X, ans;

int get(int sy, int sx, int y, int x)
{
    sy--;
    sx--;
    return pr[y][x] - pr[sy][x] - pr[y][sx] + pr[sy][sx];
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char x;
            scanf(" %c", &x);
            a[i][j] += (x - '0');
            pr[i][j] = a[i][j] + pr[i - 1][j] + pr[i][j - 1] - pr[i - 1][j - 1];
        }
    X = m;
    Y = n;
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 1; j--)
        {
            if (a[i][j])
                nxt[i][j] = nxt[i][j + 1] + 1;
            else
                nxt[i][j] = 0;
            if (a[i][j - 1] == 0 && a[i][j])
                X = min(X, nxt[i][j]);
        }

    for (int j = 1; j <= m; j++)
    {
        int y = 0;
        for (int i = 1; i <= n; i++)
        {
            if (a[i][j])
                y++;
            else
                y = 0;
            if (a[i][j] && a[i + 1][j] == 0)
                Y = min(y, Y);
        }
    }

    for (int i = 1; i <= Y; i++)
        d[i] = X;

    for (int j = 1; j <= m; j++)
    {
        int y = 0, x = X;
        for (int i = 1; i <= n; i++)
        {
            if (a[i][j] == 0)
            {
                y = 0;
                x = X;
            }
            else
            {
                y++;
                x = min(x, nxt[i][j]);
                if (j == 1 || get(i - y + 1, j - 1, i, j - 1) != y)
                    d[y] = min(x, d[y]);
            }
            //cout << i << " : " << j << " = " << y << " : " << x << endl;
        }
    }

    for (int j = 1; j <= m; j++)
    {
        int y = 0, x = X;
        for (int i = n; i >= 1; i--)
        {
            if (a[i][j] == 0)
            {
                y = 0;
                x = X;
            }
            else
            {
                y++;
                x = min(x, nxt[i][j]);
                if (j == 1 || get(i, j - 1, i + y - 1, j - 1) != y)
                    d[y] = min(x, d[y]);
            }
            //cout << i << " : " << j << " = " << y << " : " << x << endl;
        }
    }

    for (int i = 1; i <= n; i++)
        reverse(a[i] + 1, a[i] + 1 + m);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            pr[i][j] = a[i][j] + pr[i - 1][j] + pr[i][j - 1] - pr[i - 1][j - 1];

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= 1; j--)
        {
            if (a[i][j])
                nxt[i][j] = nxt[i][j + 1] + 1;
            else
                nxt[i][j] = 0;
        }

    for (int j = 1; j <= m; j++)
    {
        int y = 0, x = X;
        for (int i = 1; i <= n; i++)
        {
            if (a[i][j] == 0)
            {
                y = 0;
                x = X;
            }
            else
            {
                y++;
                x = min(x, nxt[i][j]);
                if (j == 1 || get(i - y + 1, j - 1, i, j - 1) != y)
                    d[y] = min(x, d[y]);
            }
            //cout << i << " : " << j << " = " << y << " : " << x << endl;
        }
    }

    for (int j = 1; j <= m; j++)
    {
        int y = 0, x = X;
        for (int i = n; i >= 1; i--)
        {
            if (a[i][j] == 0)
            {
                y = 0;
                x = X;
            }
            else
            {
                y++;
                x = min(x, nxt[i][j]);
                if (j == 1 || get(i, j - 1, i + y - 1, j - 1) != y)
                    d[y] = min(x, d[y]);
            }
            //cout << i << " : " << j << " = " << y << " : " << x << endl;
        }
    }

    for (int i = 1; i <= Y; i++)
    {
        //d[i + 1] = min(d[i + 1], d[i]);
        //cout << i << " : " << d[i] << endl;
        ans = max(ans, i * d[i]);
    }
    cout << ans << endl;
    return 0;
}

/*

2 2
11
10

9 9
000000000
000111000
000111000
011111110
011101110
011111110
000111000
000111000
000000000
 
9 9
000000000
000111000
000111000
011111110
011101110
011111110
000111000
000111000
000000000

6 6
000111
000111
001111
111100
111000
111000

6 6
000000
000000
001100
001111
000111
000111

6 6
000111
011111
011111
111000
111000
111000
 
*/

Compilation message

bomb.cpp: In function 'int main()':
bomb.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &x);
             ~~~~~^~~~~~~~~~~

Subtask #1

70.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	38 ms	30456 KB	Output is correct
4	Correct	38 ms	30500 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	2 ms	380 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	504 KB	Output is correct
9	Correct	2 ms	684 KB	Output is correct
10	Correct	2 ms	504 KB	Output is correct
11	Correct	2 ms	632 KB	Output is correct
12	Correct	2 ms	504 KB	Output is correct
13	Correct	2 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	2 ms	504 KB	Output is correct
16	Correct	2 ms	504 KB	Output is correct
17	Correct	3 ms	1144 KB	Output is correct
18	Correct	3 ms	1272 KB	Output is correct
19	Correct	4 ms	1528 KB	Output is correct
20	Correct	4 ms	1528 KB	Output is correct
21	Correct	3 ms	1016 KB	Output is correct
22	Correct	3 ms	1400 KB	Output is correct
23	Correct	4 ms	1656 KB	Output is correct
24	Correct	3 ms	1400 KB	Output is correct
25	Correct	4 ms	1656 KB	Output is correct
26	Correct	4 ms	1656 KB	Output is correct
27	Correct	14 ms	4860 KB	Output is correct
28	Correct	14 ms	5240 KB	Output is correct
29	Correct	19 ms	6648 KB	Output is correct
30	Correct	23 ms	7928 KB	Output is correct
31	Correct	19 ms	6264 KB	Output is correct
32	Correct	20 ms	7288 KB	Output is correct
33	Correct	25 ms	8316 KB	Output is correct
34	Correct	13 ms	5624 KB	Output is correct
35	Correct	24 ms	8312 KB	Output is correct
36	Correct	30 ms	8312 KB	Output is correct
37	Correct	2 ms	636 KB	Output is correct
38	Execution timed out	1086 ms	77616 KB	Time limit exceeded
39	Correct	2 ms	632 KB	Output is correct
40	Incorrect	152 ms	20472 KB	Output isn't correct
41	Correct	2 ms	632 KB	Output is correct
42	Correct	4 ms	1656 KB	Output is correct
43	Execution timed out	1074 ms	77624 KB	Time limit exceeded
44	Correct	27 ms	8312 KB	Output is correct
45	Execution timed out	1084 ms	77048 KB	Time limit exceeded
46	Execution timed out	1082 ms	77048 KB	Time limit exceeded
47	Execution timed out	1091 ms	77580 KB	Time limit exceeded
48	Execution timed out	1091 ms	77432 KB	Time limit exceeded
49	Execution timed out	1092 ms	77544 KB	Time limit exceeded
50	Execution timed out	1083 ms	77672 KB	Time limit exceeded
51	Execution timed out	1076 ms	78000 KB	Time limit exceeded
52	Execution timed out	1082 ms	77844 KB	Time limit exceeded
53	Execution timed out	1075 ms	78300 KB	Time limit exceeded
54	Correct	952 ms	77904 KB	Output is correct
55	Correct	944 ms	78088 KB	Output is correct
56	Execution timed out	1075 ms	77712 KB	Time limit exceeded
57	Correct	921 ms	78004 KB	Output is correct
58	Correct	929 ms	78104 KB	Output is correct
59	Correct	924 ms	77688 KB	Output is correct
60	Execution timed out	1080 ms	77772 KB	Time limit exceeded
61	Execution timed out	1086 ms	77816 KB	Time limit exceeded
62	Execution timed out	1088 ms	77816 KB	Time limit exceeded
63	Execution timed out	1083 ms	76920 KB	Time limit exceeded
64	Correct	888 ms	77308 KB	Output is correct
65	Execution timed out	1087 ms	77688 KB	Time limit exceeded
66	Execution timed out	1089 ms	76792 KB	Time limit exceeded
67	Execution timed out	1082 ms	76828 KB	Time limit exceeded
68	Execution timed out	1084 ms	77268 KB	Time limit exceeded
69	Correct	924 ms	76792 KB	Output is correct
70	Correct	467 ms	62044 KB	Output is correct
71	Correct	808 ms	77688 KB	Output is correct
72	Correct	892 ms	77560 KB	Output is correct
73	Correct	930 ms	75896 KB	Output is correct
74	Correct	910 ms	75768 KB	Output is correct
75	Correct	921 ms	76796 KB	Output is correct
76	Correct	947 ms	75912 KB	Output is correct
77	Correct	957 ms	76152 KB	Output is correct
78	Correct	951 ms	76408 KB	Output is correct
79	Correct	680 ms	75484 KB	Output is correct
80	Correct	780 ms	75996 KB	Output is correct
81	Correct	691 ms	75896 KB	Output is correct
82	Correct	971 ms	75208 KB	Output is correct
83	Correct	972 ms	75544 KB	Output is correct
84	Correct	655 ms	75928 KB	Output is correct
85	Correct	946 ms	76244 KB	Output is correct
86	Execution timed out	1075 ms	76568 KB	Time limit exceeded
87	Correct	924 ms	76752 KB	Output is correct
88	Correct	972 ms	77164 KB	Output is correct
89	Execution timed out	1080 ms	76796 KB	Time limit exceeded
90	Correct	550 ms	60408 KB	Output is correct
91	Execution timed out	1016 ms	76584 KB	Time limit exceeded
92	Execution timed out	1079 ms	76784 KB	Time limit exceeded
93	Execution timed out	1085 ms	77112 KB	Time limit exceeded
94	Execution timed out	1079 ms	77248 KB	Time limit exceeded
95	Correct	966 ms	77176 KB	Output is correct
96	Correct	975 ms	77304 KB	Output is correct
97	Execution timed out	1091 ms	77304 KB	Time limit exceeded
98	Correct	960 ms	77560 KB	Output is correct
99	Execution timed out	1063 ms	77688 KB	Time limit exceeded
100	Execution timed out	1088 ms	77536 KB	Time limit exceeded