oj.uz

Submission #9643

# Submission time Handle Problem Language Result Execution time Memory
9643 2014-09-28T07:48:06 Z jaehadad On grid (kriii2_O) C++14
1 / 4
 1000 ms 2812 KB 
#include<cstdio>
#include<cassert>
#include<cstring>
#include<map>
#include<set>
#include<time.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<utility>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int board[300][300];
bool seen[300][300];
int c[300][300];
int partial[300][300];

int rows, cols;
int psum(int y1, int y2, int x1, int x2) {
  int ret = partial[y2][x2];
  if(y1) ret -= partial[y1-1][x2];
  if(x1) ret -= partial[y2][x1-1];
  if(y1 && x1) ret += partial[y1-1][x1-1];
  return ret;
}
int go(int y, int x) {
  if(y == -1 && x == -1) return 0;
  if(y == -1 || x == -1) return -987654321;
  int& ret = c[y][x];
  if(seen[y][x]) return ret;
  seen[y][x] = true;
  ret = -987654321;
  for(int h = 1; h <= y+1; ++h)
    for(int w = 1; w <= x+1; ++w) {
      ret = max(ret,
                psum(y - h + 1, y, x - w + 1, x) + go(y - h, x - w));
    }
  // printf("go(%d,%d) = %d\n", y, x, ret);
  return ret;
}
int main() {
  cin.sync_with_stdio(false);
  cin >> rows >> cols;
  memset(partial, 0, sizeof(partial)); 
  for(int i = 0; i < rows; ++i) {
    for(int j = 0; j < cols; ++j) {
      cin >> board[i][j];
      partial[i][j] = board[i][j];
      if(i > 0) partial[i][j] += partial[i-1][j];
      if(j > 0) partial[i][j] += partial[i][j-1];
      if(i && j) partial[i][j] -= partial[i-1][j-1];
      // printf("%d ", partial[i][j]);
    }
    // printf("\n");
  }
  memset(seen, 0, sizeof(seen)); 
  cout << go(rows-1, cols-1) << endl;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2812 KB Output is correct
2 Correct 0 ms 2812 KB Output is correct
3 Correct 0 ms 2812 KB Output is correct
4 Correct 0 ms 2812 KB Output is correct
5 Correct 0 ms 2812 KB Output is correct
6 Correct 0 ms 2812 KB Output is correct
7 Correct 0 ms 2812 KB Output is correct
8 Correct 0 ms 2812 KB Output is correct
9 Correct 0 ms 2812 KB Output is correct
10 Correct 0 ms 2812 KB Output is correct
11 Correct 0 ms 2812 KB Output is correct
12 Correct 0 ms 2812 KB Output is correct
13 Correct 0 ms 2812 KB Output is correct
14 Correct 0 ms 2812 KB Output is correct
15 Correct 0 ms 2812 KB Output is correct
16 Correct 0 ms 2812 KB Output is correct
17 Correct 0 ms 2812 KB Output is correct
18 Correct 0 ms 2812 KB Output is correct
19 Correct 0 ms 2812 KB Output is correct
20 Correct 0 ms 2812 KB Output is correct
21 Correct 0 ms 2812 KB Output is correct
22 Correct 0 ms 2812 KB Output is correct
23 Correct 0 ms 2812 KB Output is correct
24 Correct 0 ms 2812 KB Output is correct
25 Correct 0 ms 2812 KB Output is correct
26 Correct 0 ms 2812 KB Output is correct
27 Correct 0 ms 2812 KB Output is correct
28 Correct 0 ms 2812 KB Output is correct
29 Correct 0 ms 2812 KB Output is correct
30 Correct 0 ms 2812 KB Output is correct

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 2812 KB Program timed out
2 Halted 0 ms 0 KB -