Submission #235772

#	Time	Username	Problem	Language	Result	Execution time	Memory
235772		Pbezz	Raisins (IOI09_raisins)	C++14	10 / 100	917 ms	35200 KiB

raisins

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

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

ll int k;

void aa(){

ll int i,j,ii,jj;

	for(i=0;i<50;i++){
	for(j=0;j<50;j++){
		for(ii=0;ii<=i;ii++){
		for(jj=0;jj<=j;jj++){
		dp[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;

}

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

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

	dp[i][j][i][j]=0;
	return 0;
}
	if(dp[i][j][ii][jj]!=INF)return dp[i][j][ii][jj];

/*
	if(j==jj&&i==ii+1){

	dp[i][j][ii][jj] = arr[i][j]+arr[ii][j];
	return 0;

	}

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

	dp[i][j][ii][jj] = arr[i][j]+arr[i][jj];
	return 0;

	}



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

	dp[i][j][ii][jj] = arr[i][j]+arr[ii][jj]+arr[ii][j]+arr[i][jj];
	dp[i][j][ii][jj]*=2;
	return 0;

	}*/

	ll int nii,njj,sum,ans=INF;

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

		for(njj=j-1;njj>=jj;njj--){
		ans=min(ans, build(i,j,ii,njj+1) + build(i,njj,ii,jj) );
		}
		//fazer o mesmo na horizontal
		for(nii=i-1;nii>=ii;nii--){
		ans=min(ans, build( i,j,nii+1,jj ) + build(nii,j,ii,jj) );
		}

		dp[i][j][ii][jj]=min(dp[i][j][ii][jj], ans+sum);

return dp[i][j][ii][jj];
}



int main(){

ll int n,m,i,j,ans;
	scanf("%lld %lld", &n, &m);



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

		scanf("%lld", &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];
		}

		}
	}

	aa();

	ans=build(n-1,m-1,0,0);
/*
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
		cout<<dp[i][j][0][0]<<" ";
	}cout<<endl;
}cout<<endl;*/
	cout<<ans<<'\n';

  
return 0; 
} 

Compilation message (stderr)

raisins.cpp: In function 'int main()':
raisins.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
raisins.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &arr[i][j]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 100