Submission #1164239

#TimeUsernameProblemLanguageResultExecution timeMemory
1164239ChottuFOrchard (NOI14_orchard)C++20
25 / 25
117 ms31664 KiB
#include <bits/stdc++.h> using namespace std; #define int long long signed main() { ios::sync_with_stdio(0); cin.tie(0); int N, M, cnt = 0; cin >> N >> M; vector<vector<int>> v(N, vector<int>(M)), cum(N+1, vector<int>(M+1, 0)); for (int n = 0; n < N; ++n) { for (int m = 0; m < M; ++m) { cin >> v[n][m]; if (v[n][m] == 0) v[n][m] = -1; else ++cnt; cum[n+1][m+1] = cum[n+1][m]+cum[n][m+1]-cum[n][m]+v[n][m]; } } int best = 0; for (int i = 0; i < N; ++i) { for (int j = i; j < N; ++j) { int mxpos = M-1; for (int m = M-1; m >= 0; --m) { if (cum[j+1][m+1]-cum[i][m+1] > cum[j+1][mxpos+1]-cum[i][mxpos+1]) mxpos = m; best = max(best, cum[j+1][mxpos+1]-cum[j+1][m]-cum[i][mxpos+1]+cum[i][m]); } } } cout << (cnt-best) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...