Submission #515950

#	Time	Username	Problem	Language	Result	Execution time	Memory
515950		Be_dos	Bomb (IZhO17_bomb)	C++17	28 / 100	1096 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;
}

//#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 / 100