10008 2024. 03. 23 23:20:15 111 Jancsi és Juliska kitalálós játéka cpp17 Időlimit túllépés 100/100 1.088s 7060 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 xxx=solve(j+1,r);
			int xx=max({solve(l,i-1),solve(i,j)});
			int x=C[i][j]+max(xx,xxx);
			if(x<a){
				a=x;
			}
			if(xxx<=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 1804 KiB
2 Időlimit túllépés 0/0 1.088s 4908 KiB
3 Elfogadva 4/4 3ms 2596 KiB
4 Elfogadva 5/5 3ms 2708 KiB
5 Elfogadva 5/5 3ms 2976 KiB
6 Elfogadva 5/5 3ms 2980 KiB
7 Elfogadva 5/5 12ms 3944 KiB
8 Elfogadva 5/5 10ms 3992 KiB
9 Elfogadva 5/5 32ms 4484 KiB
10 Elfogadva 5/5 41ms 4920 KiB
11 Elfogadva 5/5 32ms 4880 KiB
12 Elfogadva 5/5 72ms 5352 KiB
13 Elfogadva 5/5 128ms 5536 KiB
14 Elfogadva 5/5 164ms 5636 KiB
15 Elfogadva 5/5 354ms 6168 KiB
16 Elfogadva 5/5 598ms 6280 KiB
17 Elfogadva 5/5 268ms 6332 KiB
18 Elfogadva 5/5 293ms 6356 KiB
19 Elfogadva 5/5 830ms 6664 KiB
20 Elfogadva 5/5 365ms 6788 KiB
21 Elfogadva 5/5 936ms 6784 KiB
22 Elfogadva 6/6 735ms 7060 KiB