oj.uz

Submission #9514

# Submission time Handle Problem Language Result Execution time Memory
9514 2014-09-28T06:58:21 Z ainu7 On grid (kriii2_O) C++
0 / 4
 0 ms 2736 KB 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

int sum[302][302], num[300][300];
int best[300][300];

int main()
{
  int R, C;
  cin >> R >> C;
  for (int i=0; i<R; i++) for (int j=0; j<C; j++) cin >> num[i][j];

  for (int i=0; i<R; i++) for (int j=0; j<C; j++)
    sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + num[i][j];

  for (int i=0; i<C; i++) best[0][i] = sum[1][i+1];
  for (int i=1; i<R; i++) {
    for (int j=0; j<C; j++) best[i][j] = sum[i+1][j+1];
    for (int j=0; j<i; j++) {
      int last = -999999999;
      for (int k=1; k<C; k++) {
        int nxt1 = last + sum[i+1][k+1] - sum[j+1][k+1] - sum[i+1][k] + sum[j+1][k];
        best[i][k] = max(best[i][k], nxt1);
        last = max(last, nxt1);

        int nxt2 = sum[j+1][k] + sum[i+1][k+1] - sum[j+1][k+1] - sum[i+1][k] + sum[j+1][k];
        best[i][k] = max(best[i][k], nxt2);
        last = max(last, nxt2);
      }
    }
  }
  for (int i=0; i<R; i++) {
//    for (int j=0; j<C; j++) printf("%d ", best[i][j]); printf("\n");
  }

  cout << best[R-1][C-1] << endl;
}

Subtask #1
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2736 KB Output is correct
2 Incorrect 0 ms 2736 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -