103022024-03-30 13:12:23111Majomházcpp17Időlimit túllépés 10/1003.099s19404 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define INF (int)1e18

int pf[5001],dp[5001][5001];

int cost(int s,int e){
	return (pf[e]-pf[s])*(e-s);
}

int solve(int s,int e,int k){
	if(k==0){
		return cost(s,e);
	}
	int res=INF;
	int k1=k/2,k2=(k-1)/2;
	for(int i=s+k1+1;i<=e-k2-1;i++){
		res=min(res,solve(s,i,k1)+solve(i,e,k2));
	}
	return res;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K;
	cin>>N>>K;
	vector<int>v(N);
	for(int i=0;i<N;i++){
		cin>>v[i];
	}
	for(int i=0;i<N;i++){
		pf[i+1]=pf[i]+v[i];
	}
	cout<<solve(0,N,K)<<'\n';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1844 KiB
2Időlimit túllépés3.099s1432 KiB
subtask210/10
3Elfogadva3ms2440 KiB
4Elfogadva3ms2488 KiB
5Elfogadva3ms2832 KiB
6Elfogadva3ms2788 KiB
7Elfogadva3ms2972 KiB
subtask30/10
8Elfogadva354ms2940 KiB
9Időlimit túllépés3.056s3172 KiB
10Időlimit túllépés3.052s3140 KiB
11Időlimit túllépés3.056s3376 KiB
12Időlimit túllépés3.049s3332 KiB
subtask40/20
13Elfogadva216ms3556 KiB
14Időlimit túllépés3.076s3696 KiB
15Időlimit túllépés3.085s2948 KiB
16Időlimit túllépés3.082s3268 KiB
17Időlimit túllépés3.062s4220 KiB
18Időlimit túllépés3.069s4632 KiB
subtask50/29
19Futási hiba8ms5576 KiB
20Futási hiba8ms5800 KiB
21Futási hiba8ms6396 KiB
22Futási hiba8ms6712 KiB
23Futási hiba8ms7032 KiB
subtask60/31
24Futási hiba16ms8604 KiB
25Futási hiba16ms9344 KiB
26Futási hiba16ms10096 KiB
27Futási hiba16ms10892 KiB
28Futási hiba16ms11536 KiB
29Futási hiba16ms11972 KiB
30Futási hiba16ms12768 KiB
31Futási hiba16ms13444 KiB
32Futási hiba16ms13996 KiB
33Futási hiba16ms14696 KiB
34Futási hiba16ms15364 KiB
35Futási hiba16ms16036 KiB
36Futási hiba16ms16712 KiB
37Futási hiba16ms17384 KiB
38Futási hiba16ms18056 KiB
39Futási hiba16ms18600 KiB
40Futási hiba16ms19404 KiB