100052024-03-23 21:44:31111Jancsi és Juliska kitalálós játékacpp17Time limit exceeded 59/1001.1s5492 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

int N,F[300],C[300][300],A[300][300];

int solve(int l,int r){
	if(l>=r){
		return 0;
	}
	if(A[l][r]!=-1){
		return A[l][r];
	}
	int a=INT_MAX;
	for(int i=l;i<=r;i++){
		for(int j=i;j<=r;j++){
			if(i==l&&j==r){
				continue;
			}
			a=min(a,C[i][j]+max({solve(l,i-1),solve(i,j),solve(j+1,r)}));
		}
	}
	A[l][r]=a;
	return a;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>F[i];
	}
	for(int i=0;i<N;i++){
		C[i][i]=F[i];
		for(int j=i+1;j<N;j++){
			C[i][j]=max(C[i][j-1],F[j]);
		}
	}
	for(int i=0;i<N;i++){
		for(int j=i;j<N;j++){
			A[i][j]=-1;
		}
	}
	cout<<solve(0,N-1)<<'\n';
	return 0;
}
SubtaskSumTestVerdictTimeMemory
base59/100
1Accepted0/03ms2056 KiB
2Time limit exceeded0/01.1s2944 KiB
3Accepted4/43ms2712 KiB
4Accepted5/53ms2828 KiB
5Accepted5/53ms3224 KiB
6Accepted5/53ms3088 KiB
7Accepted5/534ms3904 KiB
8Accepted5/534ms4184 KiB
9Accepted5/590ms4340 KiB
10Accepted5/5116ms4476 KiB
11Accepted5/5155ms4564 KiB
12Accepted5/5307ms5048 KiB
13Accepted5/5377ms5172 KiB
14Accepted5/5460ms5492 KiB
15Time limit exceeded0/51.067s3720 KiB
16Time limit exceeded0/51.052s3900 KiB
17Time limit exceeded0/51.054s4340 KiB
18Time limit exceeded0/51.042s4300 KiB
19Time limit exceeded0/51.057s4368 KiB
20Time limit exceeded0/51.065s4500 KiB
21Time limit exceeded0/51.074s4636 KiB
22Time limit exceeded0/61.057s4872 KiB