Submission #235804

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
235804	2020-05-30T00:10:39 Z	Pbezz	Raisins (IOI09_raisins)	C++14	100 / 100	971 ms	35192 KB

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];

	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=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);

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

Compilation message

raisins.cpp: In function 'int main()':
raisins.cpp:75: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:81: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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	35072 KB	Output is correct
2	Correct	19 ms	35072 KB	Output is correct
3	Correct	19 ms	35072 KB	Output is correct
4	Correct	20 ms	35072 KB	Output is correct
5	Correct	20 ms	35072 KB	Output is correct
6	Correct	20 ms	35072 KB	Output is correct
7	Correct	20 ms	35072 KB	Output is correct
8	Correct	26 ms	35072 KB	Output is correct
9	Correct	33 ms	35072 KB	Output is correct
10	Correct	40 ms	35072 KB	Output is correct
11	Correct	38 ms	35072 KB	Output is correct
12	Correct	86 ms	35136 KB	Output is correct
13	Correct	136 ms	35072 KB	Output is correct
14	Correct	48 ms	35072 KB	Output is correct
15	Correct	179 ms	35072 KB	Output is correct
16	Correct	31 ms	35072 KB	Output is correct
17	Correct	71 ms	35072 KB	Output is correct
18	Correct	444 ms	35192 KB	Output is correct
19	Correct	805 ms	35164 KB	Output is correct
20	Correct	971 ms	35164 KB	Output is correct