Submission #262157

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
262157	2020-08-12 12:27:30	brcode	Split the sequence (APIO14_sequence)	C++14	100 / 100	734 ms	84344 KiB

sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=205;
int n,k,a[N],q[N],pre[N][M];
long long pref[N],f[N],g[N];
double slope(int i,int j) {
    if(pref[i]==pref[j]) return -1e18;
    return 1.0*((g[i]-pref[i]*pref[i])-(g[j]-pref[j]*pref[j]))/(pref[j]-pref[i]);
}
int main() {
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        pref[i] = pref[i-1]+a[i];
    } 
    for(int j=1;j<=k;++j) {
        int l=1,r=1;
        q[r]=0;
        r++;
        for(int i=1;i<=n;++i) {
            while(l<r-1 && slope(q[l],q[l+1])<=pref[i]){
                l++;
            }
            f[i]=g[q[l]]+pref[q[l]]*(pref[i]-pref[q[l]]);
            pre[i][j]=q[l];
            while(l<r-1 &&slope(q[r-2],q[r-1])>=slope(q[r-1],i)) --r;
            q[r]=i;
            r++;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29