oj.uz

Submission #873528

# Submission time Handle Problem Language Result Execution time Memory
873528 2023-11-15T09:03:50 Z dsyz Orchard (NOI14_orchard) C++17
25 / 25
 270 ms 49352 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 980 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 49228 KB Output is correct
2 Correct 73 ms 49352 KB Output is correct
3 Correct 75 ms 49104 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7008 KB Output is correct
2 Correct 15 ms 7000 KB Output is correct
3 Correct 13 ms 7004 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 604 KB Output is correct
2 Correct 8 ms 720 KB Output is correct
3 Correct 8 ms 604 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 13808 KB Output is correct
2 Correct 264 ms 13648 KB Output is correct
3 Correct 270 ms 14040 KB Output is correct