Submission #873528

#	Time	Username	Problem	Language	Result	Execution time	Memory
873528		dsyz	Orchard (NOI14_orchard)	C++17	25 / 25	270 ms	49352 KiB

orchard

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  ios_base::sync_with_stdio(false);cin.tie(0);
  ll N,M;
  ll ones = 0;
  ll sum = 0;
  cin>>N>>M;
  ll A[N + 1][M + 1];
  for(ll i = 1;i <= N;i++){
    for(ll j = 1;j <= M;j++){
      ll a;
      cin>>a;
      if(a == 0){
        A[i][j] = -1;
      }else{
        A[i][j] = 1;
        ones += 1;
      }
    }
  }
  ll ss[N + 1][M + 1];
  ll column[M + 1];
  ll arr[M + 1];
  memset(ss,0,sizeof(ss));
  memset(column,0,sizeof(column));
  memset(arr,0,sizeof(arr));
  for(ll i = 1;i <= N;i++){
    for(ll j = 1;j <= M;j++){
      ss[i][j] = ss[i - 1][j] + A[i][j];
    }
  }
  for(ll x1 = 1;x1 <= N;x1++){
    for(ll x2 = x1;x2 <= N;x2++){
      for(ll width = 1;width <= M;width++){
        arr[width] = ss[x2][width] - ss[x1 - 1][width];
      }
      for(ll width = 1;width <= M;width++){
        column[width] = max(column[width - 1] + arr[width],arr[width]);
        sum = max(sum,column[width]);
      }
    }
  }
  cout<<ones - sum<<'\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 5 / 5
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5