제출 #541403

#제출 시각아이디문제언어결과실행 시간메모리
541403nigusBomb (IZhO17_bomb)C++14
46 / 100
1105 ms79884 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define per(i, b, a) for(int i = b - 1; i >= a; i--) #define trav(a, x) for(auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef long double ld; typedef unsigned long long ull; unsigned seed = chrono::system_clock::now().time_since_epoch().count(); mt19937 eng(seed); ll random2(){ return (1ll << 31ll)*eng()+eng(); } ll n,m,k,q,T; const ll big = 1000000007; const ll big2 = 1000000009; const ll mod = 998244353; const int MAXN = 2501; bool grid[MAXN][MAXN] = {0}; bool covered[MAXN][MAXN] = {0}; int CS[MAXN][MAXN] = {0}; int sum(int i1, int j1, int i2, int j2){ return CS[i2+1][j2+1] - CS[i1][j2+1] - CS[i2+1][j1] + CS[i1][j1]; } bool can_place(int i, int j, int a, int b){ if(n-i < a || m-j < b)return 0; return (sum(i,j,i+a-1,j+b-1) == 0); rep(c1,0,a){ rep(c2,0,b){ if(!grid[i+c1][j+c2])return 0; } } return 1; } bool can_cover(int i, int j, int a, int b){ rep(dx,0,a){ rep(dy,0,b){ int i2 = i - dx; int j2 = j - dy; if(i2 >= 0 && j2 >= 0 && can_place(i2,j2,a,b))return 1; } } return 0; } bool solve(int a, int b){ rep(c1,0,n){ rep(c2,0,m){ if(grid[c1][c2] && (c1 == n-1 || !grid[c1+1][c2] || c1 == 0 || !grid[c1-1][c2]) && !can_cover(c1,c2,a,b))return 0; } } return 1; } int lft[MAXN][MAXN] = {0}; int up[MAXN][MAXN] = {0}; int mina = big; int minb = big; int main() { ios_base::sync_with_stdio(0); cin.tie(0); // freopen("fhc.txt","r",stdin); // freopen("autput.txt","w",stdout); ll a,b,c,d,e; cin >> n >> m; rep(c1,0,n){ string s; cin >> s; rep(c2,0,m){ grid[c1][c2] = (s[c2] == '1'); } } rep(c1,1,n+1){ rep(c2,1,m+1){ CS[c1][c2] = (!grid[c1-1][c2-1]) + CS[c1-1][c2] + CS[c1][c2-1] - CS[c1-1][c2-1]; } } rep(c1,0,n){ rep(c2,0,m){ if(grid[c1][c2]){ if(c1 == 0){ up[c1][c2] = 1; } else{ up[c1][c2] = up[c1-1][c2]+1; } if(c1 == n-1 || !grid[c1+1][c2])mina = min(mina, up[c1][c2]); if(c2 == 0){ lft[c1][c2] = 1; } else{ lft[c1][c2] = lft[c1][c2-1]+1; } if(c2 == m-1 || !grid[c1][c2+1])minb = min(minb, lft[c1][c2]); } } } ll ans = 0; rep(a,1,mina+1){ int lo = 1; int hi = minb+1; while(lo < hi-1){ int mid = (lo+hi)/2; if(solve(a, mid)){ lo = mid; } else{ hi = mid; } } ans = max(ans, ll(a)*ll(lo)); } cout << ans << "\n"; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bomb.cpp: In function 'int main()':
bomb.cpp:88:8: warning: unused variable 'a' [-Wunused-variable]
   88 |     ll a,b,c,d,e;
      |        ^
bomb.cpp:88:10: warning: unused variable 'b' [-Wunused-variable]
   88 |     ll a,b,c,d,e;
      |          ^
bomb.cpp:88:12: warning: unused variable 'c' [-Wunused-variable]
   88 |     ll a,b,c,d,e;
      |            ^
bomb.cpp:88:14: warning: unused variable 'd' [-Wunused-variable]
   88 |     ll a,b,c,d,e;
      |              ^
bomb.cpp:88:16: warning: unused variable 'e' [-Wunused-variable]
   88 |     ll a,b,c,d,e;
      |                ^
#Verdict Execution timeMemoryGrader output
Fetching results...