oj.uz

Submission #522423

# Submission time Handle Problem Language Result Execution time Memory
522423 2022-02-05T01:40:59 Z AndresTL Raisins (IOI09_raisins) C++11
50 / 100
 130 ms 26956 KB 
// Problem: 5634. IOI 2009 Raisins
// Contest: omegaUp
// URL: https://omegaup.com/arena/problem/IOI-2009-Raisins/
// Memory Limit: 63 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<algorithm>
using namespace std;
const int INF=2500005;
int A[52][52];
int memo[52][52][52][52];
int fr(int i1,int j1, int i2, int j2){
	if(i1==i2 && j1==j2) return 0;
	int minimo=INF;
	for(int i=i1+1;i<=i2;i++){
		minimo=min(fr(i1,j1,i-1,j2)+fr(i,j1,i2,j2),minimo);
	}
	for(int i=j1+1; i<=j2;i++){
		minimo=min(fr(i1,j1,i2,i-1)+fr(i1,i,i2,j2),minimo);
	}
	return A[i2][j2]-A[i1-1][j2]-A[i2][j1-1]+A[i1-1][j1-1]+minimo;
}
int dp(int i1,int j1, int i2, int j2){
	if(memo[i1][j1][i2][j2]!=-1) return memo[i1][j1][i2][j2];
	if(i1==i2 && j1==j2)return 0;
	int minimo=INF;
	for(int i=i1+1;i<=i2;i++){
		minimo=min(dp(i1,j1,i-1,j2)+dp(i,j1,i2,j2),minimo);
	}
	for(int i=j1+1; i<=j2;i++){
		minimo=min(dp(i1,j1,i2,i-1)+dp(i1,i,i2,j2),minimo);
	}
	memo[i1][j1][i2][j2]=A[i2][j2]-A[i1-1][j2]-A[i2][j1-1]+A[i1-1][j1-1]+minimo;
	return memo[i1][j1][i2][j2];
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>A[i][j];
			A[i][j]+=A[i-1][j]+A[i][j-1]-A[i-1][j-1];
		}
	}
	///cout<<fr(1,1,n,m)<<'\n';
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=1;k<=n;k++){
				for(int l=1;l<=m;l++){
					memo[i][j][k][l]=-1;
				}
			}
		}
	}
	cout<<dp(1,1,n,m)<<'\n';/**/
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 276 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 4 ms 3372 KB Output is correct
9 Incorrect 5 ms 4932 KB Output isn't correct
10 Incorrect 6 ms 5804 KB Output isn't correct
11 Correct 7 ms 4812 KB Output is correct
12 Incorrect 16 ms 10572 KB Output isn't correct
13 Incorrect 24 ms 13260 KB Output isn't correct
14 Correct 8 ms 6048 KB Output is correct
15 Incorrect 29 ms 14412 KB Output isn't correct
16 Incorrect 4 ms 4904 KB Output isn't correct
17 Incorrect 15 ms 9644 KB Output isn't correct
18 Incorrect 74 ms 20844 KB Output isn't correct
19 Incorrect 114 ms 25352 KB Output isn't correct
20 Incorrect 130 ms 26956 KB Output isn't correct