oj.uz

Submission #235773

# Submission time Handle Problem Language Result Execution time Memory
235773 2020-05-29T19:49:36 Z Pbezz Raisins (IOI09_raisins) C++14
10 / 100
 5000 ms 512 KB 
#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 ans+sum;
}



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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Incorrect 57 ms 248 KB Output isn't correct
6 Execution timed out 5067 ms 512 KB Time limit exceeded
7 Execution timed out 5036 ms 384 KB Time limit exceeded
8 Execution timed out 5029 ms 384 KB Time limit exceeded
9 Execution timed out 5057 ms 384 KB Time limit exceeded
10 Execution timed out 5006 ms 384 KB Time limit exceeded
11 Execution timed out 5040 ms 384 KB Time limit exceeded
12 Execution timed out 5030 ms 384 KB Time limit exceeded
13 Execution timed out 5049 ms 384 KB Time limit exceeded
14 Execution timed out 5048 ms 384 KB Time limit exceeded
15 Execution timed out 5037 ms 384 KB Time limit exceeded
16 Execution timed out 5047 ms 384 KB Time limit exceeded
17 Execution timed out 5054 ms 384 KB Time limit exceeded
18 Execution timed out 5057 ms 384 KB Time limit exceeded
19 Execution timed out 5072 ms 384 KB Time limit exceeded
20 Execution timed out 5040 ms 384 KB Time limit exceeded