제출 #662937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
662937		winterfrost	과수원 (NOI14_orchard)	C++17	12 / 25	1085 ms	19816 KiB

orchard

// 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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 0 / 5
• Subtask 4: 0 / 3
• Subtask 5: 4 / 4
• Subtask 6: 0 / 5