10301 2024. 03. 30 12:35:15 111 Majomház cpp17 Időlimit túllépés 20/100 3.099s 522324 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=1;i<=N;i++){
		cin>>v[i];
		pf[i]=pf[i-1]+v[i];
	}
	vector<vector<int>>dp(K+1,vector<int>(N+1,INF));
	vector<vector<int>>p(K+1,vector<int>(N+1));
	dp[0][0]=0;
	for(int i=1;i<=N;i++){
		dp[0][i]=pf[i]*i;
	}
	for(int i=1;i<=K;i++){
		for(int j=i;j<=N;j++){
			auto calc=[&](int k)->int{
				return dp[i-1][k]+(pf[j]-pf[k])*(j-k);
			};
			int l=0,h=j-1;
			while(h-l>=3){
				int m1=l+(h-l)/3;
				int m2=h-(h-l)/3;
				if(calc(m1)<=calc(m2)){
					h=m2;
				}
				else{
					l=m1;
				}
			}
			for(int k=0;k<=j-1;k++){
				int c=calc(k);
				if(c<dp[i][j]){
					dp[i][j]=c;
					p[i][j]=k;
				}
			}
		}
	}
	cout<<dp[K][N]<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Elfogadva 379ms 5444 KiB
subtask2 10/10
3 Elfogadva 3ms 2268 KiB
4 Elfogadva 3ms 2500 KiB
5 Elfogadva 3ms 2716 KiB
6 Elfogadva 3ms 2948 KiB
7 Elfogadva 3ms 3172 KiB
subtask3 10/10
8 Elfogadva 4ms 3452 KiB
9 Elfogadva 4ms 3664 KiB
10 Elfogadva 8ms 3892 KiB
11 Elfogadva 14ms 4104 KiB
12 Elfogadva 29ms 5144 KiB
subtask4 0/20
13 Elfogadva 64ms 4808 KiB
14 Elfogadva 107ms 5188 KiB
15 Elfogadva 215ms 6080 KiB
16 Elfogadva 870ms 11104 KiB
17 Elfogadva 2.206s 20468 KiB
18 Időlimit túllépés 3.073s 43248 KiB
subtask5 0/29
19 Időlimit túllépés 3.071s 10084 KiB
20 Időlimit túllépés 3.082s 18192 KiB
21 Időlimit túllépés 3.068s 45964 KiB
22 Időlimit túllépés 3.072s 85576 KiB
23 Időlimit túllépés 3.075s 164412 KiB
subtask6 0/31
24 Elfogadva 18ms 14656 KiB
25 Időlimit túllépés 3.099s 12536 KiB
26 Időlimit túllépés 3.066s 14628 KiB
27 Időlimit túllépés 3.065s 16908 KiB
28 Időlimit túllépés 3.042s 19148 KiB
29 Időlimit túllépés 3.073s 21640 KiB
30 Időlimit túllépés 3.066s 30076 KiB
31 Időlimit túllépés 3.029s 54180 KiB
32 Időlimit túllépés 3.069s 94236 KiB
33 Időlimit túllépés 3.066s 173328 KiB
34 Futási hiba 209ms 522324 KiB
35 Futási hiba 240ms 522296 KiB
36 Futási hiba 202ms 522280 KiB
37 Futási hiba 243ms 522024 KiB
38 Futási hiba 241ms 522012 KiB
39 Futási hiba 243ms 521984 KiB
40 Futási hiba 238ms 521976 KiB