Submission #515942

#	Time	Username	Problem	Language	Result	Execution time	Memory
515942		Be_dos	Bomb (IZhO17_bomb)	C++17	16 / 100	1095 ms	131076 KiB

bomb

#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;
}

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++)
            std::cin >> str[i];
            //for(int32_t j = 0; j < m; j++)
            //    str[i].push_back(rng() % 10 < 9 ? '1' : '0');

        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";
    }
    return 0;
}

• Subtask 1: 16 / 100