제출 #334568

#제출 시각아이디문제언어결과실행 시간메모리
334568tengiz05Bomb (IZhO17_bomb)C++17
100 / 100
326 ms87660 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define all(x) (x).begin(), (x).end() #define pb push_back #define pii pair<int, int> #define ff first #define ss second #define PI acos(-1) #define ld long double const int mod = 1e9+7, N = 2505; int msb(int val){return sizeof(int)*8-__builtin_clzll(val);} int a[N][N], n, m, k; bool usedup[N][N], usedr[N][N]; int up[N][N], down[N][N]; int ans[N]; vector<int> v[N]; vector<int> s[N]; void solve(int test_case){ int i, j; cin >> n >> m; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ char c; cin >> c; a[i][j] = (c-'0'); } } int mx=mod, my=mod; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(a[i][j] == 1){ if(usedup[i][j])continue; int t = j; int tmp = 0; while(t <= m && a[i][t] == 1){ tmp++; usedup[i][t] = true; t++; }mx = min(mx, tmp); } } } for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(a[i][j] == 1){ if(usedr[i][j])continue; int t = i; int tmp = 0; while(t <= n && a[t][j] == 1){ tmp++; usedr[t][j] = true; t++; }my = min(my, tmp); } } } if(mx == mod){ mx = 0; my = 0; } /// (mx, my) is greedy answer for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(a[i][j])up[i][j] = up[i-1][j]+a[i][j]; } } for(i=n;i>=1;i--){ for(j=1;j<=m;j++){ if(a[i][j])down[i][j] = down[i+1][j]+a[i][j]; } } for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(!a[i][j])continue; int cnt = 1; int tmp = j; while(j+1 <= m && a[i][j+1])cnt++,j++; v[i].pb(tmp); s[i].pb(cnt); } } for(i=1;i<=m;i++)ans[i] = my; for(i=1;i<=n;i++){ for(k=0;k<v[i].size();k++){ int j = v[i][k]; int sz = s[i][k]; int a=mod, b=mod, c=0; for(;sz;sz--, j++){ a = min(a, up[i][j]); b = min(b, down[i][j]); c++; ans[c] = min(ans[c], a+b-1); } } for(k=(int)v[i].size()-1;k>=0;k--){ int sz = s[i][k]; int j = v[i][k]+sz-1; int a=mod, b=mod, c=0; for(;sz;sz--, j--){ a = min(a, up[i][j]); b = min(b, down[i][j]); c++; ans[c] = min(ans[c], a+b-1); } } } // cout << mx << ' ' << my << '\n'; for(i=2;i<=mx;i++)ans[i] = min(ans[i], ans[i-1]); int res = 0; // for(i=1;i<=mx;i++)cout << ans[i] << ' '; cout << '\n'; for(i=1;i<=mx;i++)res = max(res, i*ans[i]); cout << res << '\n'; return; } signed main(){ FASTIO; #define MULTITEST 0 #if MULTITEST int ___T; cin >> ___T; for(int T_CASE = 1; T_CASE <= ___T; T_CASE++) solve(T_CASE); #else solve(1); #endif return 0; } /* 6 6 000111 011111 011111 111000 111000 111000 */

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

bomb.cpp: In function 'void solve(int)':
bomb.cpp:88:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(k=0;k<v[i].size();k++){
      |           ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...