Submission #275884

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
275884	2020-08-20T08:14:33 Z	Bill_00	Raisins (IOI09_raisins)	C++14	100 / 100	2194 ms	53624 KB

raisins

#include <bits/stdc++.h>
typedef long long ll;
const ll inf=1000000000000000000;
#define fr(i,c,d) for(ll i=c;i<=d;i++)
#define MOD 1000000007
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pp push
using namespace std;
const int sz=173;
string str(string x,int l,int r){
	string h;
	for(int i=l;i<=r;i++){
		h+=x[i];
	}
	return h;
}
ll a[2001][2001];
ll sum[51][51];
ll dp[51][51][51][51];
ll solve(int x1,int y1,int x2,int y2){
	//cout << dp[x1][y1][x2][y2] <<' ' << x1 << ' ' <<y1 << ' ' << x2 << ' ' <<  y2 << endl;
	if(dp[x1][y1][x2][y2]!=-1) return dp[x1][y1][x2][y2];
	if(x1==x2 && y1==y2) return dp[x1][y1][x2][y2]=0;
	ll res=1e18;
	for(int i=y1;i<y2;i++){
		res=min(res,solve(x1,y1,x2,i)+solve(x1,i+1,x2,y2)+sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);	
	}
	for(int i=x1;i<x2;i++){
		res=min(res,solve(x1,y1,i,y2)+solve(i+1,y1,x2,y2)+sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);
	}
	return dp[x1][y1][x2][y2]=res;
}
int main(){
	//int color[200001];
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(dp,-1,sizeof(dp));
	memset(sum,0,sizeof(sum));
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> a[i][j];
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; 
		}
	}
	//cout << solve(1,1,2,2) << endl;
	cout << solve(1,1,n,m);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	53376 KB	Output is correct
2	Correct	31 ms	53368 KB	Output is correct
3	Correct	36 ms	53368 KB	Output is correct
4	Correct	32 ms	53376 KB	Output is correct
5	Correct	32 ms	53368 KB	Output is correct
6	Correct	34 ms	53368 KB	Output is correct
7	Correct	32 ms	53368 KB	Output is correct
8	Correct	42 ms	53368 KB	Output is correct
9	Correct	51 ms	53368 KB	Output is correct
10	Correct	64 ms	53368 KB	Output is correct
11	Correct	57 ms	53368 KB	Output is correct
12	Correct	173 ms	53496 KB	Output is correct
13	Correct	260 ms	53524 KB	Output is correct
14	Correct	88 ms	53376 KB	Output is correct
15	Correct	296 ms	53624 KB	Output is correct
16	Correct	50 ms	53496 KB	Output is correct
17	Correct	120 ms	53556 KB	Output is correct
18	Correct	744 ms	53588 KB	Output is correct
19	Correct	1635 ms	53624 KB	Output is correct
20	Correct	2194 ms	53608 KB	Output is correct