10321 2024. 03. 30 18:09:04 111 Majomház cpp17 Időlimit túllépés 40/100 3.099s 7564 KiB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define INF (int)1e18

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K;
	cin>>N>>K;
	vector<int>v(N+1),pf(N+1);
	for(int i=0;i<N;i++){
		cin>>v[i];
		pf[i+1]=pf[i]+v[i];
	}
	auto cost=[&](int s,int e)->int{
		return (pf[e]-pf[s])*(e-s);
	};
	auto solve=[&](int y)->pair<int,int>{
		vector<int>dp(N+1),cnt(N+1);
		for(int i=1;i<=N;i++){
			dp[i]=cost(0,i);
			cnt[i]=0;
			for(int j=1;j<i;j++){
				int x=dp[j]+cost(j,i)+y;
				if(x<dp[i]){
					dp[i]=x;
					cnt[i]=cnt[j]+1;
				}
			}
		}
		return{dp[N],cnt[N]};
	};
	int l=0,h=INF;
	while(l<h){
		int m=(l+h)/2;
		auto [x,c]=solve(m);
		if(c<=K){
			h=m;
		}
		else{
			l=m+1;
		}
	}
	auto [x,c]=solve(h);
	cout<<x-c*h<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 2092 KiB
2 Elfogadva 1.039s 2416 KiB
subtask2 10/10
3 Elfogadva 3ms 2444 KiB
4 Elfogadva 3ms 2508 KiB
5 Elfogadva 3ms 2740 KiB
6 Elfogadva 3ms 2772 KiB
7 Elfogadva 3ms 2960 KiB
subtask3 10/10
8 Elfogadva 14ms 3068 KiB
9 Elfogadva 16ms 3264 KiB
10 Elfogadva 16ms 3352 KiB
11 Elfogadva 16ms 3608 KiB
12 Elfogadva 16ms 3560 KiB
subtask4 20/20
13 Elfogadva 1.246s 3888 KiB
14 Elfogadva 1.271s 3808 KiB
15 Elfogadva 1.299s 4056 KiB
16 Elfogadva 1.322s 4184 KiB
17 Elfogadva 1.325s 4184 KiB
18 Elfogadva 1.328s 4384 KiB
subtask5 0/29
19 Időlimit túllépés 3.065s 5136 KiB
20 Időlimit túllépés 3.069s 5056 KiB
21 Időlimit túllépés 3.059s 4984 KiB
22 Időlimit túllépés 3.065s 4996 KiB
23 Időlimit túllépés 3.051s 5180 KiB
subtask6 0/31
24 Időlimit túllépés 3.042s 6956 KiB
25 Időlimit túllépés 3.066s 7228 KiB
26 Időlimit túllépés 3.065s 7244 KiB
27 Időlimit túllépés 3.059s 7376 KiB
28 Időlimit túllépés 3.039s 7332 KiB
29 Időlimit túllépés 3.073s 7440 KiB
30 Időlimit túllépés 3.055s 7308 KiB
31 Időlimit túllépés 3.062s 7364 KiB
32 Időlimit túllépés 3.059s 7352 KiB
33 Időlimit túllépés 3.099s 7344 KiB
34 Időlimit túllépés 3.055s 7564 KiB
35 Időlimit túllépés 3.071s 7384 KiB
36 Időlimit túllépés 3.062s 7420 KiB
37 Időlimit túllépés 3.058s 7440 KiB
38 Időlimit túllépés 3.062s 7296 KiB
39 Időlimit túllépés 3.066s 7424 KiB
40 Időlimit túllépés 3.049s 7392 KiB