10005 2024. 03. 23 21:44:31 111 Jancsi és Juliska kitalálós játéka cpp17 Időlimit túllépés 59/100 1.1s 5492 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 59/100
1 Elfogadva 0/0 3ms 2056 KiB
2 Időlimit túllépés 0/0 1.1s 2944 KiB
3 Elfogadva 4/4 3ms 2712 KiB
4 Elfogadva 5/5 3ms 2828 KiB
5 Elfogadva 5/5 3ms 3224 KiB
6 Elfogadva 5/5 3ms 3088 KiB
7 Elfogadva 5/5 34ms 3904 KiB
8 Elfogadva 5/5 34ms 4184 KiB
9 Elfogadva 5/5 90ms 4340 KiB
10 Elfogadva 5/5 116ms 4476 KiB
11 Elfogadva 5/5 155ms 4564 KiB
12 Elfogadva 5/5 307ms 5048 KiB
13 Elfogadva 5/5 377ms 5172 KiB
14 Elfogadva 5/5 460ms 5492 KiB
15 Időlimit túllépés 0/5 1.067s 3720 KiB
16 Időlimit túllépés 0/5 1.052s 3900 KiB
17 Időlimit túllépés 0/5 1.054s 4340 KiB
18 Időlimit túllépés 0/5 1.042s 4300 KiB
19 Időlimit túllépés 0/5 1.057s 4368 KiB
20 Időlimit túllépés 0/5 1.065s 4500 KiB
21 Időlimit túllépés 0/5 1.074s 4636 KiB
22 Időlimit túllépés 0/6 1.057s 4872 KiB