Submission #235805

#	Time	Username	Problem	Language	Result	Execution time	Memory
235805		Pbezz	Raisins (IOI09_raisins)	C++14	100 / 100	977 ms	38776 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<52;i++){
	for(j=0;j<52;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] - presum[i][jj-1]; 
	ans += ( presum[ii-1][jj-1] - presum[ii-1][j] );
	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];

	ll int nii,njj,sum=getsum(i,j,ii,jj),ans=INF;
 
		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=1;i<=n;i++){
		for(j=1;j<=m;j++){ 
 
		scanf("%lld", &arr[i][j]);
		presum[i][j]=presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]+arr[i][j];

		}
	}
	aa();
 
	ans=build(n,m,1,1);

	cout<<ans<<'\n';
  
return 0; 
} 

Compilation message (stderr)

raisins.cpp: In function 'int main()':
raisins.cpp:59: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:64: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