Submission #155953

#TimeUsernameProblemLanguageResultExecution timeMemory
155953MinnakhmetovOrchard (NOI14_orchard)C++14
25 / 25
185 ms12152 KiB
#include <bits/stdc++.h> #define ll long long #define all(aaa) aaa.begin(), aaa.end() using namespace std; const int INF = 1e9 + 5, N = 1e6 + 5; int n, m; int a[N]; vector<vector<int>> v; int calc(int h) { int mn = 0, ans = INF; for (int i = 1; i <= m; i++) { ans = min(ans, mn + i * h - a[i] * 2); mn = min(mn, a[i] * 2 - i * h); } return ans; } int solve() { v.resize(n + 1, vector<int>(m + 1)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> v[i][j]; v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1]; } } int ans = INF; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j++) { for (int k = 1; k <= m; k++) { a[k] = v[j][k] - v[i - 1][k]; } ans = min(ans, calc(j - i + 1) + v[n][m]); } } return ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; cout << solve(); return 0; }
#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...