oj.uz

Submission #124608

# Submission time Handle Problem Language Result Execution time Memory
124608 2019-07-03T14:58:35 Z Touubs Orchard (NOI14_orchard) C++17
25 / 25
 281 ms 14252 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 12524 KB Output is correct
2 Correct 273 ms 14012 KB Output is correct
3 Correct 273 ms 14252 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2796 KB Output is correct
2 Correct 58 ms 2724 KB Output is correct
3 Correct 56 ms 2672 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 11 ms 548 KB Output is correct
3 Correct 10 ms 504 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 6804 KB Output is correct
2 Correct 281 ms 7736 KB Output is correct
3 Correct 281 ms 7800 KB Output is correct