제출 #907298

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
907298	2024-01-15 11:00:31	daoquanglinh2007	Bomb (IZhO17_bomb)	C++17	41 / 100	1102 ms	55888 KiB

bomb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int NM = 2500, inf = 1e9+7;
int N, M, f[NM+5][NM+5], dp[NM+5][NM+5], ans = 0, H = +inf, W = +inf;
char a[NM+5][NM+5];
int getf(int x, int y, int u, int v){
  return f[u][v]-f[x-1][v]-f[u][y-1]+f[x-1][y-1];
}
bool check(int r, int c){
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= M; j++) dp[i][j] = 0;
  
  for (int i = 1; i+r-1 <= N; i++)
    for (int j = 1; j+c-1 <= M; j++)
      if (getf(i, j, i+r-1, j+c-1) == r*c){
        dp[i][j]++;
        dp[i+r][j]--;
        dp[i][j+c]--;
        dp[i+r][j+c]++;
      }
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= M; j++){
      dp[i][j] += dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
      if (dp[i][j] == 0 && a[i][j] == '1') return 0;
    }
  return 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 41 / 100