10006 2024. 03. 23 23:15:30 111 Jancsi és Juliska kitalálós játéka cpp17 Időlimit túllépés 100/100 1.001s 6696 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;
			}
			int xx=max({solve(l,i-1),solve(i,j),solve(j+1,r)});
			int x=C[i][j]+xx;
			if(x<a){
				a=x;
			}
			if(solve(j+1,r)<xx)break;
		}
	}
	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 100/100
1 Elfogadva 0/0 3ms 1924 KiB
2 Időlimit túllépés 0/0 1.001s 5064 KiB
3 Elfogadva 4/4 3ms 2580 KiB
4 Elfogadva 5/5 3ms 2608 KiB
5 Elfogadva 5/5 3ms 3016 KiB
6 Elfogadva 5/5 3ms 3140 KiB
7 Elfogadva 5/5 12ms 3900 KiB
8 Elfogadva 5/5 10ms 4032 KiB
9 Elfogadva 5/5 34ms 4536 KiB
10 Elfogadva 5/5 39ms 4560 KiB
11 Elfogadva 5/5 32ms 4548 KiB
12 Elfogadva 5/5 71ms 4956 KiB
13 Elfogadva 5/5 125ms 5008 KiB
14 Elfogadva 5/5 157ms 5340 KiB
15 Elfogadva 5/5 342ms 5796 KiB
16 Elfogadva 5/5 563ms 5996 KiB
17 Elfogadva 5/5 259ms 6380 KiB
18 Elfogadva 5/5 287ms 6388 KiB
19 Elfogadva 5/5 772ms 6572 KiB
20 Elfogadva 5/5 354ms 6696 KiB
21 Elfogadva 5/5 882ms 6604 KiB
22 Elfogadva 6/6 689ms 6608 KiB