Submission #124608

#	Time	Username	Problem	Language	Result	Execution time	Memory
124608		Touubs	Orchard (NOI14_orchard)	C++17	25 / 25	281 ms	14252 KiB

orchard

#include <bits/stdc++.h>
using namespace std;
#define dout if(false) cout

int lookup(vector<vector<int>>& prefixSumGrid, int x, int y) {
  dout << "lookup(" << x << ", " << y << ")" << endl;
  if (x < 0 || y < 0) {
    dout << " = 0\n";
    return 0;
  }
  dout << "           = " << prefixSumGrid[y][x] << "\n";
  return prefixSumGrid[y][x];
  return 1;
}

signed main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> grid(n, vector<int>(m));
  vector<vector<int>> verticalPrefixSum(n, vector<int>(m));
  int originalCost = 0;

  int in;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> in;
      grid[i][j] = 2 * in - 1;
      originalCost += in;
      dout << originalCost << " ";
    }
  }
  dout << endl;
  for (int j = 0; j < m; j++) {
    verticalPrefixSum[0][j] = grid[0][j];
    for (int i = 1; i < n; i++) {
      verticalPrefixSum[i][j] = verticalPrefixSum[i-1][j] + grid[i][j];
    }
  }
  for (auto a : verticalPrefixSum) {
    for (auto b : a) {
      dout << b << " " ;
    }
    dout << endl;
  }

  int best = -1;

  for (int bottom = -1; bottom < n; bottom++) {
    for (int top = bottom + 1; top < n; top++) {
      int right = 0;
      int result = 0;
      while (right < m) {
        result += lookup(verticalPrefixSum, right, top) - lookup(verticalPrefixSum, right, bottom);
        right++;
        result = max(result, 0);
        best = max(result, best);
      }
    }
  }

  cout << originalCost-best << endl;

}

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