103022024-03-30 13:12:23111Majomházcpp17Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1844 KiB
2Time limit exceeded3.099s1432 KiB
subtask210/10
3Accepted3ms2440 KiB
4Accepted3ms2488 KiB
5Accepted3ms2832 KiB
6Accepted3ms2788 KiB
7Accepted3ms2972 KiB
subtask30/10
8Accepted354ms2940 KiB
9Time limit exceeded3.056s3172 KiB
10Time limit exceeded3.052s3140 KiB
11Time limit exceeded3.056s3376 KiB
12Time limit exceeded3.049s3332 KiB
subtask40/20
13Accepted216ms3556 KiB
14Time limit exceeded3.076s3696 KiB
15Time limit exceeded3.085s2948 KiB
16Time limit exceeded3.082s3268 KiB
17Time limit exceeded3.062s4220 KiB
18Time limit exceeded3.069s4632 KiB
subtask50/29
19Runtime error8ms5576 KiB
20Runtime error8ms5800 KiB
21Runtime error8ms6396 KiB
22Runtime error8ms6712 KiB
23Runtime error8ms7032 KiB
subtask60/31
24Runtime error16ms8604 KiB
25Runtime error16ms9344 KiB
26Runtime error16ms10096 KiB
27Runtime error16ms10892 KiB
28Runtime error16ms11536 KiB
29Runtime error16ms11972 KiB
30Runtime error16ms12768 KiB
31Runtime error16ms13444 KiB
32Runtime error16ms13996 KiB
33Runtime error16ms14696 KiB
34Runtime error16ms15364 KiB
35Runtime error16ms16036 KiB
36Runtime error16ms16712 KiB
37Runtime error16ms17384 KiB
38Runtime error16ms18056 KiB
39Runtime error16ms18600 KiB
40Runtime error16ms19404 KiB