Submission #9372

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9372	2014-09-28T05:59:52 Z	maniac	On grid (kriii2_O)	C++	0 / 4	0 ms	111408 KB

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(){
	freopen("in.txt", "r", stdin);
	//freopen("input.txt", "r", stdin);
	solve();


}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	0 ms	111408 KB	open (syscall #2) was called by the program (disallowed syscall)
2	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 3.0

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