Submission #275884

#	Time	Username	Problem	Language	Result	Execution time	Memory
275884		Bill_00	Raisins (IOI09_raisins)	C++14	100 / 100	2194 ms	53624 KiB

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 / 100