10302 2024. 03. 30 13:12:23 111 Majomház cpp17 Időlimit túllépés 10/100 3.099s 19404 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1844 KiB
2 Időlimit túllépés 3.099s 1432 KiB
subtask2 10/10
3 Elfogadva 3ms 2440 KiB
4 Elfogadva 3ms 2488 KiB
5 Elfogadva 3ms 2832 KiB
6 Elfogadva 3ms 2788 KiB
7 Elfogadva 3ms 2972 KiB
subtask3 0/10
8 Elfogadva 354ms 2940 KiB
9 Időlimit túllépés 3.056s 3172 KiB
10 Időlimit túllépés 3.052s 3140 KiB
11 Időlimit túllépés 3.056s 3376 KiB
12 Időlimit túllépés 3.049s 3332 KiB
subtask4 0/20
13 Elfogadva 216ms 3556 KiB
14 Időlimit túllépés 3.076s 3696 KiB
15 Időlimit túllépés 3.085s 2948 KiB
16 Időlimit túllépés 3.082s 3268 KiB
17 Időlimit túllépés 3.062s 4220 KiB
18 Időlimit túllépés 3.069s 4632 KiB
subtask5 0/29
19 Futási hiba 8ms 5576 KiB
20 Futási hiba 8ms 5800 KiB
21 Futási hiba 8ms 6396 KiB
22 Futási hiba 8ms 6712 KiB
23 Futási hiba 8ms 7032 KiB
subtask6 0/31
24 Futási hiba 16ms 8604 KiB
25 Futási hiba 16ms 9344 KiB
26 Futási hiba 16ms 10096 KiB
27 Futási hiba 16ms 10892 KiB
28 Futási hiba 16ms 11536 KiB
29 Futási hiba 16ms 11972 KiB
30 Futási hiba 16ms 12768 KiB
31 Futási hiba 16ms 13444 KiB
32 Futási hiba 16ms 13996 KiB
33 Futási hiba 16ms 14696 KiB
34 Futási hiba 16ms 15364 KiB
35 Futási hiba 16ms 16036 KiB
36 Futási hiba 16ms 16712 KiB
37 Futási hiba 16ms 17384 KiB
38 Futási hiba 16ms 18056 KiB
39 Futási hiba 16ms 18600 KiB
40 Futási hiba 16ms 19404 KiB