oj.uz

Submission #662937

# Submission time Handle Problem Language Result Execution time Memory
662937 2022-11-26T13:39:07 Z winterfrost Orchard (NOI14_orchard) C++17
12 / 25
 1000 ms 19816 KB 
// Author: winterfrost (TLX account: Todoroki_Shouto)
// Contest: Singapore National Olympiad in Informatics 2014
// Problem: A. Orchard

# include <bits/stdc++.h>
using namespace std;

# define GRIND ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int main() {
  GRIND

  // For subtasks with small constraints

  int n, m;  cin >> n >> m;
  
  char tree[n + 1][m + 1];
  int alex = 0, bert = 0;
  int prefAlex[n + 1][m + 1];
  int prefBert[n + 1][m + 1];
  memset(prefAlex, 0, sizeof(prefAlex));
  memset(prefBert, 0, sizeof(prefBert));
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      cin >> tree[i][j];
      if(tree[i][j] == '0') alex++;
      else bert++;
      prefAlex[i][j] = prefAlex[i - 1][j] + prefAlex[i][j - 1] - prefAlex[i - 1][j - 1] + (tree[i][j] == '0' ? 1 : 0);
      prefBert[i][j] = prefBert[i - 1][j] + prefBert[i][j - 1] - prefBert[i - 1][j - 1] + (tree[i][j] == '1' ? 1 : 0);
    }
  } 
  
  int ans = INT_MAX;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      for(int k = i; k <= n; k++) {
        for(int l = j; l <= m; l++) {
          int apples = prefAlex[k][l] - prefAlex[i - 1][l] - prefAlex[k][j - 1] + prefAlex[i - 1][j - 1];
          int bananas = prefBert[k][l] - prefBert[i - 1][l] - prefBert[k][j - 1] + prefBert[i - 1][j - 1];
          int cost = (bert - bananas) + apples;
          ans = min(ans, cost);
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 588 KB Output is correct
2 Correct 175 ms 588 KB Output is correct
3 Correct 167 ms 596 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 19816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 3284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 460 KB Output is correct
2 Correct 206 ms 536 KB Output is correct
3 Correct 212 ms 540 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 8392 KB Time limit exceeded
2 Halted 0 ms 0 KB -