oj.uz

Submission #515948

# Submission time Handle Problem Language Result Execution time Memory
515948 2022-01-20T07:42:16 Z Be_dos Bomb (IZhO17_bomb) C++17
30 / 100
 1000 ms 131076 KB 
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

bool good(std::string* str, int32_t n, int32_t m, int32_t ans_h, int32_t ans_w) {
    int32_t** sums = new int32_t*[n];
    for(int32_t i = 0; i < n; i++) {
        sums[i] = new int32_t[m];
        for(int32_t j = 0; j < m; j++)
            sums[i][j] = 0;
    }

    for(int32_t i = 0; i <= n - ans_h; i++) {
        for(int32_t j = 0; j <= m - ans_w; j++) {
            int32_t sum = 0;
            for(int32_t k = i; k < i + ans_h; k++)
                for(int32_t q = j; q < j + ans_w; q++) {
                    sum += str[k][q] - '0';
                }
            if(sum != ans_h * ans_w)
                continue;

            for(int32_t k = i; k < i + ans_h; k++)
                for(int32_t q = j; q < j + ans_w; q++) {
                    sums[k][q]++;
                }
        }
    }

    bool good = true;
    for(int32_t i = 0; i < n; i++)
        for(int32_t j = 0 ;j < m; j++)
            if(str[i][j] == '1' && sums[i][j] == 0)
                good = false;
    return good;
}

//#define TEST

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int32_t n, m;
    std::cin >> n >> m;

    std::mt19937 rng;
    for(int32_t z = 0; z < 1; z++) {
        std::string* str = new std::string[n];
        for(int32_t i = 0; i < n; i++)
#ifndef TEST
            std::cin >> str[i];
#else
            for(int32_t j = 0; j < m; j++)
                str[i].push_back(rng() % 10 < 9 ? '1' : '0');
#endif

        int32_t ans2 = 0;
        int32_t max_w = m;
        for(int32_t i = 1; i <= n; i++) {
            while(max_w > 0 && !good(str, n, m, i, max_w))
                max_w--;
            ans2 = std::max(ans2, i * max_w);
        }
        std::cout << ans2;

#ifdef TEST
        int32_t ans = 0;
        for(int32_t i = 1; i <= n; i++)
            for(int32_t j = 1; j <= m; j++)
                if(good(str, n, m, i, j))
                    ans = std::max(ans, i * j);
        std::cout << ans << "\n";
        int a = 0;
        if(ans != ans2)
            a++;
#endif
    }
    return 0;
}

/*
 11111
 11111
 11011
 01111
 00111
 */

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 12 ms 4152 KB Output is correct
4 Correct 20 ms 5808 KB Output is correct
5 Execution timed out 1080 ms 14092 KB Time limit exceeded
6 Correct 158 ms 4080 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 316 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 5 ms 1612 KB Output is correct
18 Correct 3 ms 1472 KB Output is correct
19 Correct 10 ms 3136 KB Output is correct
20 Correct 13 ms 3572 KB Output is correct
21 Correct 8 ms 2124 KB Output is correct
22 Correct 11 ms 3132 KB Output is correct
23 Correct 43 ms 5372 KB Output is correct
24 Correct 9 ms 2640 KB Output is correct
25 Correct 38 ms 5944 KB Output is correct
26 Correct 47 ms 4892 KB Output is correct
27 Execution timed out 1063 ms 74720 KB Time limit exceeded
28 Execution timed out 1093 ms 90424 KB Time limit exceeded
29 Execution timed out 1042 ms 80760 KB Time limit exceeded
30 Execution timed out 1096 ms 104988 KB Time limit exceeded
31 Execution timed out 1090 ms 94772 KB Time limit exceeded
32 Execution timed out 1083 ms 99136 KB Time limit exceeded
33 Execution timed out 1097 ms 110840 KB Time limit exceeded
34 Correct 583 ms 79672 KB Output is correct
35 Execution timed out 1098 ms 110852 KB Time limit exceeded
36 Execution timed out 1094 ms 81956 KB Time limit exceeded
37 Correct 1 ms 336 KB Output is correct
38 Runtime error 216 ms 131076 KB Execution killed with signal 9
39 Correct 0 ms 332 KB Output is correct
40 Runtime error 645 ms 131076 KB Execution killed with signal 9
41 Correct 1 ms 332 KB Output is correct
42 Correct 243 ms 6448 KB Output is correct
43 Runtime error 161 ms 131076 KB Execution killed with signal 9
44 Execution timed out 1089 ms 106056 KB Time limit exceeded
45 Runtime error 156 ms 131076 KB Execution killed with signal 9
46 Runtime error 159 ms 131076 KB Execution killed with signal 9
47 Runtime error 155 ms 131076 KB Execution killed with signal 9
48 Runtime error 154 ms 131076 KB Execution killed with signal 9
49 Runtime error 195 ms 131076 KB Execution killed with signal 9
50 Runtime error 156 ms 131076 KB Execution killed with signal 9
51 Runtime error 152 ms 131076 KB Execution killed with signal 9
52 Runtime error 160 ms 131076 KB Execution killed with signal 9
53 Runtime error 150 ms 131076 KB Execution killed with signal 9
54 Runtime error 152 ms 131076 KB Execution killed with signal 9
55 Runtime error 179 ms 131076 KB Execution killed with signal 9
56 Runtime error 182 ms 131076 KB Execution killed with signal 9
57 Runtime error 159 ms 131076 KB Execution killed with signal 9
58 Runtime error 155 ms 131076 KB Execution killed with signal 9
59 Runtime error 151 ms 131076 KB Execution killed with signal 9
60 Runtime error 151 ms 131076 KB Execution killed with signal 9
61 Runtime error 197 ms 131076 KB Execution killed with signal 9
62 Runtime error 194 ms 131076 KB Execution killed with signal 9
63 Runtime error 201 ms 131076 KB Execution killed with signal 9
64 Runtime error 161 ms 131076 KB Execution killed with signal 9
65 Runtime error 159 ms 131076 KB Execution killed with signal 9
66 Runtime error 148 ms 131076 KB Execution killed with signal 9
67 Runtime error 159 ms 131076 KB Execution killed with signal 9
68 Runtime error 149 ms 131076 KB Execution killed with signal 9
69 Runtime error 150 ms 131076 KB Execution killed with signal 9
70 Runtime error 183 ms 131076 KB Execution killed with signal 9
71 Runtime error 148 ms 131076 KB Execution killed with signal 9
72 Runtime error 152 ms 131076 KB Execution killed with signal 9
73 Runtime error 159 ms 131076 KB Execution killed with signal 9
74 Runtime error 159 ms 131076 KB Execution killed with signal 9
75 Runtime error 156 ms 131076 KB Execution killed with signal 9
76 Runtime error 153 ms 131076 KB Execution killed with signal 9
77 Runtime error 175 ms 131076 KB Execution killed with signal 9
78 Runtime error 153 ms 131076 KB Execution killed with signal 9
79 Runtime error 151 ms 131076 KB Execution killed with signal 9
80 Runtime error 160 ms 131076 KB Execution killed with signal 9
81 Runtime error 167 ms 131076 KB Execution killed with signal 9
82 Runtime error 155 ms 131076 KB Execution killed with signal 9
83 Runtime error 186 ms 131076 KB Execution killed with signal 9
84 Runtime error 149 ms 131076 KB Execution killed with signal 9
85 Runtime error 146 ms 131076 KB Execution killed with signal 9
86 Runtime error 162 ms 131076 KB Execution killed with signal 9
87 Runtime error 182 ms 131076 KB Execution killed with signal 9
88 Runtime error 157 ms 131076 KB Execution killed with signal 9
89 Runtime error 180 ms 131076 KB Execution killed with signal 9
90 Runtime error 185 ms 131076 KB Execution killed with signal 9
91 Runtime error 187 ms 131076 KB Execution killed with signal 9
92 Runtime error 149 ms 131076 KB Execution killed with signal 9
93 Runtime error 153 ms 131076 KB Execution killed with signal 9
94 Runtime error 174 ms 131076 KB Execution killed with signal 9
95 Runtime error 149 ms 131076 KB Execution killed with signal 9
96 Runtime error 163 ms 131076 KB Execution killed with signal 9
97 Runtime error 153 ms 131076 KB Execution killed with signal 9
98 Runtime error 179 ms 131076 KB Execution killed with signal 9
99 Runtime error 174 ms 131076 KB Execution killed with signal 9
100 Runtime error 152 ms 131076 KB Execution killed with signal 9