Submission #9373

#	Time	Username	Problem	Language	Result	Execution time	Memory
9373		maniac	On grid (kriii2_O)	C++98	4 / 4	88 ms	111416 KiB

O

#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>
#include<limits>
   
using namespace std;

long long gcd( long long b, long long s ){
	return (s!=0) ? gcd( s, b%s ) : b;
}
#define LL long long
#define INF -1000000007
int r,c,a[303][303],s[303][303],d[303][303][303],D[303][303],re;

void solve(){
	scanf("%d %d",&r,&c);
	for(int i = 1; i <= r; i++){
		for(int j = 1; j<= c; j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i = 1; i<= r; i++){
		for(int j =1 ; j<= c; j++){
			s[i][j] = s[i][j-1] + a[i][j];
			
		}
	}

	for(int i= 0; i<= r; i++){
		for(int j =0  ; j <=c; j++){
			D[i][j] = INF;
			for(int k = 0 ; k<= c; k++)
				d[i][j][k] = INF;
		}
	}
	re = INF;

	
	d[0][0][1] = 0;
	D[0][0] = 0;
	for(int i = 1 ; i<=r; i++){
		for(int j =1 ; j <=c; j++){
			for(int k = 1; j-k >= 0; k++){
				d[i][j][k] = max(D[i-1][j-k],d[i-1][j][k]) + s[i][j]-s[i][j-k];
				D[i][j] = max(D[i][j],d[i][j][k]);
			}
		}
	}
	for(int i = 1; i <=c ; i++)
		re = max(re,d[r][c][i]);

	printf("%d\n",re);
}

int main(){
	
	solve();


}

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3