10007 2024. 03. 23 23:18:16 111 Jancsi és Juliska kitalálós játéka cpp17 Időlimit túllépés 90/100 1.1s 7412 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));
			int x=C[i][j]+max(xx,solve(j+1,r));
			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 90/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 2936 KiB
5 Elfogadva 5/5 3ms 3324 KiB
6 Elfogadva 5/5 3ms 2996 KiB
7 Elfogadva 5/5 14ms 3924 KiB
8 Elfogadva 5/5 13ms 4012 KiB
9 Elfogadva 5/5 41ms 4412 KiB
10 Elfogadva 5/5 48ms 4824 KiB
11 Elfogadva 5/5 41ms 5080 KiB
12 Elfogadva 5/5 87ms 5444 KiB
13 Elfogadva 5/5 158ms 5752 KiB
14 Elfogadva 5/5 201ms 5732 KiB
15 Elfogadva 5/5 442ms 6376 KiB
16 Elfogadva 5/5 750ms 6636 KiB
17 Elfogadva 5/5 333ms 6964 KiB
18 Elfogadva 5/5 368ms 7180 KiB
19 Időlimit túllépés 0/5 1.046s 7376 KiB
20 Elfogadva 5/5 453ms 7412 KiB
21 Időlimit túllépés 0/5 1.067s 5108 KiB
22 Elfogadva 6/6 916ms 7356 KiB