Submission #9554

#	Time	Username	Problem	Language	Result	Execution time	Memory
9554		ainu7	On grid (kriii2_O)	C++98	4 / 4	80 ms	2736 KiB

O

#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];
//    num[i][j] = rand() % 10 - 5;
//    printf("%d ", num[i][j]);
  }
//  printf("\n");
  }
//  printf("\n");

  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<R; i++) {
    for (int j=0; j<C; j++) {
      best[i][j] = sum[i+1][j+1];
      for (int k=0; k<i; k++) for (int l=0; l<j; l++)
        best[i][j] = max(best[i][j], best[k][l] + sum[i+1][j+1] - sum[i+1][l+1] - sum[k+1][j+1] + sum[k+1][l+1]);
      printf("%d ", best[i][j]);
    }
    printf("\n");
  }
  printf("%d\n", best[R-1][C-1]);*/
  // ;;

  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);

        int nxt2 = best[j][k-1] + 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);
//if (i == 3 && j == 2)        printf("%d %d %d %d %d\n", j, k, last, nxt1, nxt2);
        last = max(nxt1, 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: 1 / 1
• Subtask 2: 3 / 3