Submission #235779

#	Time	Username	Problem	Language	Result	Execution time	Memory
235779		Pbezz	Raisins (IOI09_raisins)	C++14	100 / 100	929 ms	35448 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[ii-1][j];
	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: 100 / 100