oj.uz

Submission #235768

# Submission time Handle Problem Language Result Execution time Memory
235768 2020-05-29T18:30:19 Z Pbezz Raisins (IOI09_raisins) C++14
10 / 100
 5000 ms 51576 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 100000
#define MAXN 55
typedef pair<ll int,ll int> pii; 

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

ll int kk;

void aa(){

ll int i,j,ii,jj;

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

}

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

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

	mapi[i][j][i][j]=0;
	return;
}

	ll int nii,njj,sum;

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

		for(njj=j-1;njj>=jj;njj--){
	//auto d=make_pair( make_pair(i,j), make_pair(ii,njj+1) );
		if(mapi[i][j][ii][njj+1]==INF){
		build(i,j,ii,njj+1);
		}

		kk = mapi[i][j][ii][njj+1]+sum;

	//d=make_pair( make_pair(i,njj), make_pair(ii,jj) );
		if(mapi[i][njj][ii][jj]==INF){
		build(i,njj,ii,jj);
		}

		kk+=mapi[i][njj][ii][jj];

	 //d=make_pair( make_pair(i,j), make_pair(ii,jj) );

	mapi[i][j][ii][jj] = min( mapi[i][j][ii][jj],kk );

		}
		//fazer o mesmo na horizontal

		for(nii=i-1;nii>=ii;nii--){

	//auto d=make_pair( make_pair(i,j), make_pair(nii+1,jj) );
		if(mapi[i][j][nii+1][jj]==INF){
		build(i,j,nii+1,jj);
		}

		kk = mapi[i][j][nii+1][jj]+sum;	//if(i==1&&j==1&&ii==0&&jj==1)cout<<k<<"\n";

	//d=make_pair( make_pair(nii,j), make_pair(ii,jj) );
		if(mapi[nii][j][ii][jj]==INF){ 
		build(nii,j,ii,jj);
		}

		kk+=mapi[nii][j][ii][jj]; //if(i==1&&j==1&&ii==0&&jj==1)cout<<k<<"\n";

	 //d=make_pair( make_pair(i,j), make_pair(ii,jj) );

	mapi[i][j][ii][jj] = min( mapi[i][j][ii][jj],kk );

		}

}



int main(){

ll int n,m,i,ii,jj,j,sum,k;
	cin>>n>>m;

	ll int arr[n][m];

	for(i=0;i<n;i++){
		for(j=0;j<m;j++){ dp[i][j]=INF;

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

		}
	}dp[0][0]=0;

	aa();

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

		sum=presum[i][j];

		for(jj=j-1;jj>=0;jj--){

		k=dp[i][jj]+sum;

	//auto d=make_pair( make_pair(i,j), make_pair(0,jj+1) );
		if(mapi[i][j][0][jj+1]==INF){ 
		build(i,j,0,jj+1);
		}

		k+=mapi[i][j][0][jj+1]; 

		dp[i][j]=min(dp[i][j], k);


		}
		//fazer o mesmo na horizontal

		for(ii=i-1;ii>=0;ii--){ 

		k=dp[ii][j]+sum;

	//auto d=make_pair( make_pair(i,j), make_pair(ii+1,0) );
		if(mapi[i][j][ii+1][0]==INF){
		build(i,j,ii+1,0);
		}

		k+=mapi[i][j][ii+1][0];	//if(i==1&&j==1)cout<<k<<" "<<dp[i][j]<<endl<<endl;

		dp[i][j]=min(dp[i][j], k);

		}


		}
	}

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

	cout<<dp[i][j]<<" ";

	}cout<<endl;
}*/
cout<<dp[n-1][m-1]<<'\n';

  
return 0; 
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 51456 KB Output is correct
2 Correct 31 ms 51320 KB Output is correct
3 Incorrect 29 ms 51456 KB Output isn't correct
4 Incorrect 30 ms 51448 KB Output isn't correct
5 Incorrect 30 ms 51456 KB Output isn't correct
6 Incorrect 29 ms 51456 KB Output isn't correct
7 Execution timed out 5065 ms 51456 KB Time limit exceeded
8 Execution timed out 5065 ms 51448 KB Time limit exceeded
9 Execution timed out 5069 ms 51448 KB Time limit exceeded
10 Execution timed out 5074 ms 51456 KB Time limit exceeded
11 Execution timed out 5075 ms 51456 KB Time limit exceeded
12 Execution timed out 5085 ms 51576 KB Time limit exceeded
13 Execution timed out 5073 ms 51456 KB Time limit exceeded
14 Execution timed out 5081 ms 51456 KB Time limit exceeded
15 Execution timed out 5082 ms 51456 KB Time limit exceeded
16 Execution timed out 5041 ms 51448 KB Time limit exceeded
17 Execution timed out 5072 ms 51456 KB Time limit exceeded
18 Execution timed out 5069 ms 51456 KB Time limit exceeded
19 Execution timed out 5080 ms 51456 KB Time limit exceeded
20 Execution timed out 5076 ms 51456 KB Time limit exceeded