oj.uz

Submission #515950

# Submission time Handle Problem Language Result Execution time Memory
515950 2022-01-20T07:47:12 Z Be_dos Bomb (IZhO17_bomb) C++17
28 / 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 ans_w = m;
        for(int32_t i = 0; i < n; i++) {
            int32_t len = 0;
            for(int32_t j = 0; j < m; j++)
                if(str[i][j] == '1') {
                    len++;
                } else if(len > 0) {
                    ans_w = std::min(ans_w, len);
                    len = 0;
                }
            if(len > 0)
                ans_w = std::min(ans_w, len);
        }

        int32_t ans2 = 0;
        int32_t max_h = n;
        for(int32_t i = 1; i <= ans_w; i++) {
            while(max_h > 0 && !good(str, n, m, max_h, i))
                max_h--;
            ans2 = std::max(ans2, i * max_h);
        }
        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
28.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 Execution timed out 1086 ms 96776 KB Time limit exceeded
4 Execution timed out 1083 ms 100264 KB Time limit exceeded
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 5 ms 1484 KB Output is correct
18 Correct 9 ms 1612 KB Output is correct
19 Correct 19 ms 3596 KB Output is correct
20 Correct 18 ms 3780 KB Output is correct
21 Correct 4 ms 1356 KB Output is correct
22 Correct 10 ms 2620 KB Output is correct
23 Correct 47 ms 5668 KB Output is correct
24 Correct 12 ms 2624 KB Output is correct
25 Correct 36 ms 5660 KB Output is correct
26 Correct 72 ms 4380 KB Output is correct
27 Execution timed out 1079 ms 38356 KB Time limit exceeded
28 Execution timed out 1090 ms 73340 KB Time limit exceeded
29 Execution timed out 1080 ms 47152 KB Time limit exceeded
30 Execution timed out 1090 ms 78192 KB Time limit exceeded
31 Execution timed out 1081 ms 79356 KB Time limit exceeded
32 Execution timed out 1076 ms 74996 KB Time limit exceeded
33 Execution timed out 1086 ms 77288 KB Time limit exceeded
34 Execution timed out 1080 ms 61788 KB Time limit exceeded
35 Execution timed out 1093 ms 80544 KB Time limit exceeded
36 Execution timed out 1089 ms 43700 KB Time limit exceeded
37 Correct 1 ms 332 KB Output is correct
38 Runtime error 584 ms 131076 KB Execution killed with signal 9
39 Correct 1 ms 332 KB Output is correct
40 Execution timed out 1096 ms 110252 KB Time limit exceeded
41 Correct 0 ms 332 KB Output is correct
42 Correct 229 ms 6460 KB Output is correct
43 Runtime error 560 ms 131076 KB Execution killed with signal 9
44 Execution timed out 1091 ms 74956 KB Time limit exceeded
45 Runtime error 419 ms 131076 KB Execution killed with signal 9
46 Runtime error 416 ms 131076 KB Execution killed with signal 9
47 Runtime error 494 ms 131076 KB Execution killed with signal 9
48 Runtime error 448 ms 131076 KB Execution killed with signal 9
49 Execution timed out 1068 ms 130316 KB Time limit exceeded
50 Runtime error 511 ms 131076 KB Execution killed with signal 9
51 Runtime error 475 ms 131076 KB Execution killed with signal 9
52 Runtime error 456 ms 131076 KB Execution killed with signal 9
53 Runtime error 460 ms 131076 KB Execution killed with signal 9
54 Runtime error 471 ms 131076 KB Execution killed with signal 9
55 Runtime error 498 ms 131076 KB Execution killed with signal 9
56 Runtime error 516 ms 131076 KB Execution killed with signal 9
57 Runtime error 464 ms 131076 KB Execution killed with signal 9
58 Runtime error 451 ms 131076 KB Execution killed with signal 9
59 Runtime error 476 ms 131076 KB Execution killed with signal 9
60 Runtime error 500 ms 131076 KB Execution killed with signal 9
61 Execution timed out 1040 ms 130316 KB Time limit exceeded
62 Runtime error 624 ms 131076 KB Execution killed with signal 9
63 Execution timed out 1089 ms 130380 KB Time limit exceeded
64 Runtime error 606 ms 131076 KB Execution killed with signal 9
65 Runtime error 474 ms 131076 KB Execution killed with signal 9
66 Runtime error 444 ms 131076 KB Execution killed with signal 9
67 Runtime error 503 ms 131076 KB Execution killed with signal 9
68 Runtime error 663 ms 131076 KB Execution killed with signal 9
69 Runtime error 475 ms 131076 KB Execution killed with signal 9
70 Runtime error 333 ms 131076 KB Execution killed with signal 9
71 Runtime error 496 ms 131076 KB Execution killed with signal 9
72 Runtime error 478 ms 131076 KB Execution killed with signal 9
73 Runtime error 435 ms 131072 KB Execution killed with signal 9
74 Runtime error 424 ms 131076 KB Execution killed with signal 9
75 Runtime error 510 ms 131076 KB Execution killed with signal 9
76 Runtime error 434 ms 131076 KB Execution killed with signal 9
77 Runtime error 422 ms 131076 KB Execution killed with signal 9
78 Runtime error 466 ms 131076 KB Execution killed with signal 9
79 Runtime error 519 ms 131076 KB Execution killed with signal 9
80 Runtime error 472 ms 131076 KB Execution killed with signal 9
81 Runtime error 425 ms 131076 KB Execution killed with signal 9
82 Runtime error 410 ms 131076 KB Execution killed with signal 9
83 Runtime error 452 ms 131076 KB Execution killed with signal 9
84 Runtime error 402 ms 131076 KB Execution killed with signal 9
85 Runtime error 481 ms 131076 KB Execution killed with signal 9
86 Runtime error 479 ms 131076 KB Execution killed with signal 9
87 Runtime error 537 ms 131076 KB Execution killed with signal 9
88 Runtime error 501 ms 131076 KB Execution killed with signal 9
89 Runtime error 473 ms 131076 KB Execution killed with signal 9
90 Runtime error 319 ms 131076 KB Execution killed with signal 9
91 Runtime error 469 ms 131076 KB Execution killed with signal 9
92 Runtime error 458 ms 131076 KB Execution killed with signal 9
93 Runtime error 417 ms 131076 KB Execution killed with signal 9
94 Runtime error 403 ms 131076 KB Execution killed with signal 9
95 Runtime error 403 ms 131076 KB Execution killed with signal 9
96 Runtime error 456 ms 131076 KB Execution killed with signal 9
97 Runtime error 448 ms 131076 KB Execution killed with signal 9
98 Runtime error 508 ms 131076 KB Execution killed with signal 9
99 Runtime error 472 ms 131076 KB Execution killed with signal 9
100 Runtime error 470 ms 131076 KB Execution killed with signal 9