Submission #1102874

#TimeUsernameProblemLanguageResultExecution timeMemory
1102874KasymKBomb (IZhO17_bomb)C++17
99 / 100
325 ms110668 KiB
#include "bits/stdc++.h" using namespace std; #define ff first #define ss second #define all(v) v.begin(), v.end() #define ll long long #define pb push_back #define pii pair<int, int> #define pli pair<ll, int> #define pll pair<ll, ll> #define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i) #define wr puts("----------------") template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;} template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;} const int N = 2505; int cep[N][N], sag[N][N], up[N][N], as[N][N], c[N]; char a[N][N]; int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) scanf(" %c", &a[i][j]); for(int i = 1; i <= n; ++i){ for(int j = 1; j <= m; ++j) cep[i][j] = (a[i][j]=='1'?cep[i][j-1]+1:0); for(int j = m; j >= 1; --j) sag[i][j] = (a[i][j]=='1'?sag[i][j+1]+1:0); } for(int j = 1; j <= m; ++j){ for(int i = 1; i <= n; ++i) up[i][j] = (a[i][j]=='1'?up[i-1][j]+1:0); for(int i = n; i >= 1; --i) as[i][j] = (a[i][j]=='1'?as[i+1][j]+1:0); } int A = n, B = m; for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(a[i][j] == '1') umin(A, up[i][j]+as[i][j]-1), umin(B, cep[i][j]+sag[i][j]-1); for(int i = 1; i <= A; ++i) c[i] = B; for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j){ if(a[i][j] != '1') continue; int now = B; if(as[i][j]==1) for(int k = i; k >= i-A+1; --k){ if(cep[i][j]==1) umin(now, sag[k][j]), umin(c[i-k+1], now); if(sag[i][j]==1) umin(now, cep[k][j]), umin(c[i-k+1], now); } else if(up[i][j]==1) for(int k = i; k <= i+A-1; ++k){ if(cep[i][j]==1) umin(now, sag[k][j]), umin(c[k-i+1], now); if(sag[i][j]==1) umin(now, cep[k][j]), umin(c[k-i+1], now); } } int answer = 0; for(int i = 1; i <= A; ++i) umax(answer, i*c[i]); printf("%d\n", answer); }

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
bomb.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |             scanf(" %c", &a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...