oj.uz

답안 #423299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
423299 2021-06-10T23:04:55 Z antimirage Bomb (IZhO17_bomb) C++14
52 / 100
 963 ms 75104 KB 
/*
 *  let's for fixed width X find the maximum valid height Y, denote it by ans[X]. 
 *  upper bound of Y for every X is ans[1].
 *   
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>

using namespace std;

int main() {
    int n, m, res = 0;
    cin >> n >> m;
    vector <vector <int>> a(n + 5, vector<int>(m + 5, 0));
    for (int i = 1; i <= n; i++) {
        scanf("\n");
        for (int j = 1; j <= m; j++) {
            char ch;
            scanf("%c", &ch);
            a[i][j] = ch - 48;
        }
    }
    vector <vector <int>> up(n + 5, vector<int>(m + 5, 0));
    vector <vector <int>> dn(n + 5, vector<int>(m + 5, 0));
    
    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            up[i][j] = a[i][j] ? up[i - 1][j] + 1 : 0;
        }
        for (int i = n; i >= 1; i--) {
            dn[i][j] = a[i][j] ? dn[i + 1][j] + 1 : 0;
        }
    }
    vector <int> ans(m + 5, n);
    for (int t = 0; t < 2; t++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i][j])
                    ans[1] = min(ans[1], up[i][j] + dn[i][j] - 1);
            }
            for (int j = 1; j <= m; j++) {
                if (a[i][j] && !a[i][j - 1]) {
                    
                    int min_d = n, min_u = n, k;
                    for (k = j; k <= m && a[i][k]; k++) {
                        min_d = min(min_d, dn[i][k]);
                        min_u = min(min_u, up[i][k]);
                        ans[k - j + 1] = min(ans[k - j + 1], min_d + min_u - 1);
                    } 
                    ans[k - j + 1] = 0;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                swap(a[i][j], a[i][m - j + 1]);
                swap(up[i][j], up[i][m - j + 1]);
                swap(dn[i][j], dn[i][m - j + 1]);
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        ans[i] = min(ans[i], ans[i - 1]);
        res = max(res, i * ans[i]);
        //cout << i << " --> " << ans[i] << endl;
    }
    cout << res << endl;
}

Compilation message

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

Subtask #1
52.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 1 ms 204 KB Output isn't correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 1 ms 204 KB Output isn't correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Incorrect 1 ms 204 KB Output isn't correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Incorrect 2 ms 292 KB Output isn't correct
20 Incorrect 1 ms 332 KB Output isn't correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Incorrect 2 ms 432 KB Output isn't correct
24 Incorrect 1 ms 332 KB Output isn't correct
25 Incorrect 2 ms 332 KB Output isn't correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 10 ms 1344 KB Output is correct
28 Incorrect 11 ms 1740 KB Output isn't correct
29 Incorrect 14 ms 1868 KB Output isn't correct
30 Incorrect 21 ms 2760 KB Output isn't correct
31 Correct 15 ms 2220 KB Output is correct
32 Incorrect 16 ms 2372 KB Output isn't correct
33 Incorrect 24 ms 2852 KB Output isn't correct
34 Incorrect 9 ms 1356 KB Output isn't correct
35 Incorrect 21 ms 2976 KB Output isn't correct
36 Correct 21 ms 2980 KB Output is correct
37 Incorrect 1 ms 204 KB Output isn't correct
38 Correct 963 ms 74992 KB Output is correct
39 Incorrect 1 ms 204 KB Output isn't correct
40 Correct 109 ms 10304 KB Output is correct
41 Correct 1 ms 204 KB Output is correct
42 Correct 2 ms 332 KB Output is correct
43 Correct 855 ms 74984 KB Output is correct
44 Correct 23 ms 2892 KB Output is correct
45 Incorrect 883 ms 75008 KB Output isn't correct
46 Correct 877 ms 74988 KB Output is correct
47 Incorrect 881 ms 74988 KB Output isn't correct
48 Correct 861 ms 74984 KB Output is correct
49 Correct 892 ms 74988 KB Output is correct
50 Correct 924 ms 75076 KB Output is correct
51 Correct 874 ms 74972 KB Output is correct
52 Correct 914 ms 74984 KB Output is correct
53 Correct 885 ms 74988 KB Output is correct
54 Correct 878 ms 74988 KB Output is correct
55 Incorrect 859 ms 74984 KB Output isn't correct
56 Correct 899 ms 75104 KB Output is correct
57 Incorrect 862 ms 75096 KB Output isn't correct
58 Correct 888 ms 74988 KB Output is correct
59 Correct 796 ms 74984 KB Output is correct
60 Correct 806 ms 74988 KB Output is correct
61 Correct 834 ms 75000 KB Output is correct
62 Correct 834 ms 74948 KB Output is correct
63 Correct 851 ms 75076 KB Output is correct
64 Correct 847 ms 74968 KB Output is correct
65 Correct 826 ms 75100 KB Output is correct
66 Correct 825 ms 74992 KB Output is correct
67 Correct 815 ms 74860 KB Output is correct
68 Correct 858 ms 74776 KB Output is correct
69 Correct 818 ms 74944 KB Output is correct
70 Incorrect 499 ms 48324 KB Output isn't correct
71 Incorrect 795 ms 74868 KB Output isn't correct
72 Incorrect 801 ms 74860 KB Output isn't correct
73 Correct 806 ms 74948 KB Output is correct
74 Incorrect 788 ms 74824 KB Output isn't correct
75 Incorrect 790 ms 74884 KB Output isn't correct
76 Incorrect 804 ms 74840 KB Output isn't correct
77 Incorrect 799 ms 74844 KB Output isn't correct
78 Incorrect 828 ms 74864 KB Output isn't correct
79 Incorrect 785 ms 74696 KB Output isn't correct
80 Incorrect 781 ms 74848 KB Output isn't correct
81 Incorrect 839 ms 74732 KB Output isn't correct
82 Incorrect 809 ms 74732 KB Output isn't correct
83 Incorrect 792 ms 74732 KB Output isn't correct
84 Incorrect 799 ms 74820 KB Output isn't correct
85 Incorrect 800 ms 74820 KB Output isn't correct
86 Incorrect 874 ms 74836 KB Output isn't correct
87 Incorrect 789 ms 74852 KB Output isn't correct
88 Correct 788 ms 74836 KB Output is correct
89 Correct 806 ms 74728 KB Output is correct
90 Incorrect 504 ms 48200 KB Output isn't correct
91 Incorrect 821 ms 74600 KB Output isn't correct
92 Incorrect 791 ms 74608 KB Output isn't correct
93 Incorrect 826 ms 74604 KB Output isn't correct
94 Correct 828 ms 74824 KB Output is correct
95 Incorrect 819 ms 74692 KB Output isn't correct
96 Correct 796 ms 74580 KB Output is correct
97 Incorrect 833 ms 74564 KB Output isn't correct
98 Incorrect 800 ms 74604 KB Output isn't correct
99 Incorrect 804 ms 74604 KB Output isn't correct
100 Incorrect 836 ms 74632 KB Output isn't correct