Submission #907308

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
907308	2024-01-15 11:13:09	daoquanglinh2007	Bomb (IZhO17_bomb)	C++17	58 / 100	1061 ms	55892 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];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int get_rand(int l, int r){
  int tmp = rng()%(r-l+1);
  if (tmp < 0) tmp += r-l+1;
  return l + tmp;
}
 
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]--;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 58 / 100