Submission #235768

#	Time	Username	Problem	Language	Result	Execution time	Memory
235768		Pbezz	Raisins (IOI09_raisins)	C++14	10 / 100	5085 ms	51576 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 100000
#define MAXN 55
typedef pair<ll int,ll int> pii; 

ll int mapi[51][51][51][51];//mapi[i][j][ii][jj] é answer para a submatriz 
ll int presum[MAXN][MAXN];
ll int dp[MAXN][MAXN];

ll int kk;

void aa(){

ll int i,j,ii,jj;

	for(i=0;i<50;i++){
	for(j=0;j<50;j++){
		for(ii=0;ii<50;ii++){
		for(jj=0;jj<50;jj++){
		mapi[i][j][ii][jj]=INF;
	}
	}
}
}

}

ll int getsum(ll int i,ll int j, ll int ii, ll int jj){

	ll int ans=presum[i][j];

	if(jj==0&&ii==0)return ans;

	if(ii==0){
	ans-=presum[i][jj-1];
	return ans;
	}

	if(jj==0){
	ans-=presum[ii-1][j];
	return ans;
	}

	ans-=presum[i][jj-1]; 
	ans-=presum[j][ii-1];
	ans+=presum[ii-1][jj-1];
	return ans;

}

void build(ll int i,ll int j,ll int ii,ll int jj){

	if(i==ii&&j==jj){

	mapi[i][j][i][j]=0;
	return;
}

	ll int nii,njj,sum;

		sum=getsum(i,j,ii,jj);

		for(njj=j-1;njj>=jj;njj--){
	//auto d=make_pair( make_pair(i,j), make_pair(ii,njj+1) );
		if(mapi[i][j][ii][njj+1]==INF){
		build(i,j,ii,njj+1);
		}

		kk = mapi[i][j][ii][njj+1]+sum;

	//d=make_pair( make_pair(i,njj), make_pair(ii,jj) );
		if(mapi[i][njj][ii][jj]==INF){
		build(i,njj,ii,jj);
		}

		kk+=mapi[i][njj][ii][jj];

	 //d=make_pair( make_pair(i,j), make_pair(ii,jj) );

	mapi[i][j][ii][jj] = min( mapi[i][j][ii][jj],kk );

		}
		//fazer o mesmo na horizontal

		for(nii=i-1;nii>=ii;nii--){

	//auto d=make_pair( make_pair(i,j), make_pair(nii+1,jj) );
		if(mapi[i][j][nii+1][jj]==INF){
		build(i,j,nii+1,jj);
		}

		kk = mapi[i][j][nii+1][jj]+sum;	//if(i==1&&j==1&&ii==0&&jj==1)cout<<k<<"\n";

	//d=make_pair( make_pair(nii,j), make_pair(ii,jj) );
		if(mapi[nii][j][ii][jj]==INF){ 
		build(nii,j,ii,jj);
		}

		kk+=mapi[nii][j][ii][jj]; //if(i==1&&j==1&&ii==0&&jj==1)cout<<k<<"\n";

	 //d=make_pair( make_pair(i,j), make_pair(ii,jj) );

	mapi[i][j][ii][jj] = min( mapi[i][j][ii][jj],kk );

		}

}



int main(){

ll int n,m,i,ii,jj,j,sum,k;
	cin>>n>>m;

	ll int arr[n][m];

	for(i=0;i<n;i++){
		for(j=0;j<m;j++){ dp[i][j]=INF;

		cin>>arr[i][j];
		if(i==0&&j==0){presum[i][j]=arr[0][0]; continue;}

		if(i==0){
		presum[i][j]=presum[i][j-1]+arr[i][j];
		}else if(j==0){
		presum[i][j]=presum[i-1][j]+arr[i][j];
		}else{
		presum[i][j]=presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]+arr[i][j];
		}

		}
	}dp[0][0]=0;

	aa();

	for(i=0;i<n;i++){
		for(j=0;j<m;j++){

		sum=presum[i][j];

		for(jj=j-1;jj>=0;jj--){

		k=dp[i][jj]+sum;

	//auto d=make_pair( make_pair(i,j), make_pair(0,jj+1) );
		if(mapi[i][j][0][jj+1]==INF){ 
		build(i,j,0,jj+1);
		}

		k+=mapi[i][j][0][jj+1]; 

		dp[i][j]=min(dp[i][j], k);


		}
		//fazer o mesmo na horizontal

		for(ii=i-1;ii>=0;ii--){ 

		k=dp[ii][j]+sum;

	//auto d=make_pair( make_pair(i,j), make_pair(ii+1,0) );
		if(mapi[i][j][ii+1][0]==INF){
		build(i,j,ii+1,0);
		}

		k+=mapi[i][j][ii+1][0];	//if(i==1&&j==1)cout<<k<<" "<<dp[i][j]<<endl<<endl;

		dp[i][j]=min(dp[i][j], k);

		}


		}
	}

/*
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){

	cout<<dp[i][j]<<" ";

	}cout<<endl;
}*/
cout<<dp[n-1][m-1]<<'\n';

  
return 0; 
} 

• Subtask 1: 10 / 100