제출 #1314663

#제출 시각아이디문제언어결과실행 시간메모리
1314663joshjuice과수원 (NOI14_orchard)C++20
25 / 25
109 ms8248 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;

#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define ppf pop_front
#define pf push_front
#define bk back()
#define frnt front()
#define ins insert
#define er erase
#define sc second
#define fr first
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define REP(i,n) for (int i = 0; i < n; ++i)
#define REP1(i,n) for (int i = 1; i <= n; ++i)
#define REPV(i,n) for (int i = n-1; i >= 0; --i)
#define REPV1(i, n) for (int i = n; i > 0; --i)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define MNTO(x,y) x = min(x, (__typeof__(x))y)
#define MXTO(x,y) x = max(x, (__typeof__(x))y)

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vi> s(n, vi(m));
  REP(i, n) {
    REP(j, m) cin >> s[i][j];
  }
  int totbanana = 0;
  REP(i, n) {
    REP(j, m) {
      totbanana += s[i][j];
    }
  }
  int ans = INT_MAX;
  vector<int> a(m);
  REP(r1, n) {
    fill(ALL(a), 0);
    for (int r2 = r1; r2 < n; ++r2) {
      REP(c, m) a[c] += s[r2][c];
      int height = r2-r1+1;
      int bh = 0, bo = INT_MIN;
      REP(c, m) {
        int x = 2*a[c]-height;
        bh = max(x, bh+x);
        MXTO(bo, bh);
      }
      MNTO(ans, totbanana-bo);
    }
  }
  cout << ans;
  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...