oj.uz

답안 #915555

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915555 2024-01-24T07:08:24 Z vjudge1 Bomb (IZhO17_bomb) C++17
41 / 100
 1000 ms 104624 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include <bits/stdc++.h>
 
#define int long long 
#define pb push_back
#define ui unsigned int
#define ld long double
#define pl pair<long long int,  long long int>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ff first    
#define ss second
#define sz size()
#define all(x) x.begin(), x.end()
 
using namespace std;
 
const int maxn = 1e6 + 11;
const int inf = 1e17 + 1;
const int mod = 1e9 + 7;
// const int mod = 998244353;
const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1 , 0, -1, 1, -1, 1};
const double eps = 1e-10;

int n, m;

int pr[2501][2501], p[2501][2501];

void solve() {
    cin >> n >> m;

    char ch[n + 1][m + 1];
    int cnt = 0;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> ch[ i ][ j ];
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            pr[ i ][ j ] = pr[i - 1][ j ] + pr[ i ][j - 1] - pr[i - 1][j - 1] + (ch[ i ][ j ] - '0');
        }
    }
    int y = m;
    int x = 1;
    int ans = 0;

    while(x <= n && y) {
        int l = 1, r = y;
        int anss = 0;
        while(l <= r) {
            int mid = l + r >> 1;
            for(int i = 0; i <= n; i++) {
                for(int j = 0; j <= m; j++) {
                    p[ i ][ j ] = 0;
                }
            }
            for(int i = 0; i + x <= n; i++) {
                for(int j = 0; j + mid <= m; j++) {
                    int c = pr[i + x][j + mid] - pr[i + x][ j ] - pr[ i ][j + mid] + pr[ i ][ j ];

                    if(c == x * mid) {
                        p[i + x + 1][j + mid + 1]++;
                        p[i + 1][j + mid + 1]--;
                        p[i + x + 1][j + 1]--;
                        p[i + 1][j + 1]++;
                    }
                }
            }

            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= m; j++) {
                    p[ i ][ j ] += p[i - 1][ j ] + p[ i ][j - 1] - p[i - 1][j - 1];
                }
            }
            bool fl = true;
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= m; j++) {
                    if(ch[ i ][ j ] == '1' && p[ i ][ j ] == 0) {
                        fl = false;
                        break;
                    }
                }
            }
            if(fl) {
                anss = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        y = anss;
        ans = max(ans, x * y);
        x++;
    }
    cout << ans;
}
    
signed main() {
    // freopen("sum.in", "r", stdin); 
    // freopen("sum.out", "w", stdout);
 
    boost;      

    int tt = 1;

    // cin >> tt;

    for(int i = 1; i <= tt; i++) {
        // cout << "Case " << i << ":\n";
        solve();    
    }           
}

Compilation message

bomb.cpp: In function 'void solve()':
bomb.cpp:55:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |             int mid = l + r >> 1;
      |                       ~~^~~
bomb.cpp:35:9: warning: unused variable 'cnt' [-Wunused-variable]
   35 |     int cnt = 0;
      |         ^~~

Subtask #1
41.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 16 ms 57948 KB Output is correct
4 Correct 16 ms 57948 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2624 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 2 ms 2908 KB Output is correct
20 Correct 2 ms 2908 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 1 ms 2904 KB Output is correct
23 Correct 3 ms 2908 KB Output is correct
24 Correct 2 ms 2904 KB Output is correct
25 Correct 3 ms 2908 KB Output is correct
26 Correct 3 ms 2908 KB Output is correct
27 Correct 6 ms 8536 KB Output is correct
28 Correct 10 ms 8796 KB Output is correct
29 Correct 234 ms 11376 KB Output is correct
30 Correct 79 ms 15448 KB Output is correct
31 Correct 64 ms 11388 KB Output is correct
32 Correct 63 ms 11612 KB Output is correct
33 Correct 115 ms 15452 KB Output is correct
34 Correct 9 ms 10844 KB Output is correct
35 Correct 25 ms 15512 KB Output is correct
36 Correct 253 ms 15700 KB Output is correct
37 Correct 1 ms 2396 KB Output is correct
38 Incorrect 510 ms 104368 KB Output isn't correct
39 Correct 1 ms 2396 KB Output is correct
40 Execution timed out 1054 ms 32860 KB Time limit exceeded
41 Correct 1 ms 2392 KB Output is correct
42 Correct 7 ms 2904 KB Output is correct
43 Incorrect 451 ms 104468 KB Output isn't correct
44 Correct 761 ms 15696 KB Output is correct
45 Incorrect 443 ms 104464 KB Output isn't correct
46 Incorrect 353 ms 104276 KB Output isn't correct
47 Incorrect 447 ms 104460 KB Output isn't correct
48 Incorrect 434 ms 104476 KB Output isn't correct
49 Incorrect 509 ms 104472 KB Output isn't correct
50 Incorrect 444 ms 104528 KB Output isn't correct
51 Incorrect 433 ms 104360 KB Output isn't correct
52 Incorrect 428 ms 104464 KB Output isn't correct
53 Incorrect 423 ms 104624 KB Output isn't correct
54 Incorrect 365 ms 104352 KB Output isn't correct
55 Incorrect 375 ms 104460 KB Output isn't correct
56 Incorrect 598 ms 104352 KB Output isn't correct
57 Incorrect 379 ms 104468 KB Output isn't correct
58 Incorrect 378 ms 104352 KB Output isn't correct
59 Incorrect 367 ms 104272 KB Output isn't correct
60 Incorrect 394 ms 104460 KB Output isn't correct
61 Incorrect 505 ms 104476 KB Output isn't correct
62 Incorrect 524 ms 104480 KB Output isn't correct
63 Incorrect 517 ms 104472 KB Output isn't correct
64 Incorrect 356 ms 104368 KB Output isn't correct
65 Incorrect 426 ms 104472 KB Output isn't correct
66 Incorrect 452 ms 104368 KB Output isn't correct
67 Incorrect 448 ms 104568 KB Output isn't correct
68 Incorrect 471 ms 104532 KB Output isn't correct
69 Incorrect 379 ms 104532 KB Output isn't correct
70 Execution timed out 1065 ms 84756 KB Time limit exceeded
71 Execution timed out 1069 ms 104276 KB Time limit exceeded
72 Execution timed out 1055 ms 104276 KB Time limit exceeded
73 Execution timed out 1060 ms 104368 KB Time limit exceeded
74 Execution timed out 1036 ms 104276 KB Time limit exceeded
75 Execution timed out 1060 ms 104372 KB Time limit exceeded
76 Execution timed out 1036 ms 104352 KB Time limit exceeded
77 Execution timed out 1045 ms 104368 KB Time limit exceeded
78 Execution timed out 1073 ms 104276 KB Time limit exceeded
79 Execution timed out 1016 ms 104272 KB Time limit exceeded
80 Execution timed out 1045 ms 104364 KB Time limit exceeded
81 Execution timed out 1008 ms 104272 KB Time limit exceeded
82 Execution timed out 1052 ms 104368 KB Time limit exceeded
83 Execution timed out 1067 ms 104348 KB Time limit exceeded
84 Execution timed out 1049 ms 104356 KB Time limit exceeded
85 Incorrect 371 ms 104272 KB Output isn't correct
86 Incorrect 511 ms 104352 KB Output isn't correct
87 Incorrect 369 ms 104272 KB Output isn't correct
88 Execution timed out 1018 ms 104356 KB Time limit exceeded
89 Incorrect 414 ms 104272 KB Output isn't correct
90 Execution timed out 1074 ms 84820 KB Time limit exceeded
91 Incorrect 395 ms 104612 KB Output isn't correct
92 Incorrect 416 ms 104484 KB Output isn't correct
93 Incorrect 508 ms 104532 KB Output isn't correct
94 Incorrect 417 ms 104532 KB Output isn't correct
95 Execution timed out 1016 ms 104352 KB Time limit exceeded
96 Execution timed out 1066 ms 104368 KB Time limit exceeded
97 Incorrect 509 ms 104476 KB Output isn't correct
98 Execution timed out 1058 ms 104276 KB Time limit exceeded
99 Incorrect 413 ms 104276 KB Output isn't correct
100 Incorrect 504 ms 104480 KB Output isn't correct