Submission #329262

#	Time	Username	Problem	Language	Result	Execution time	Memory
329262		jovan_b	Split the sequence (APIO14_sequence)	C++17	100 / 100	977 ms	81188 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

ll pre[100005];
ll dp[100005];
ll dpp[100005];
int prosli[205][100005];

struct line{
    ll a, b;
    int ind;
    ll eval(ll x){
        return a*x+b;
    }
    ll intersect(line g){
        return -floor(1.0*(b-g.b)/(a-g.a));
    }
};

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);

    int n, k;
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        int x;
        cin >> x;
        pre[i] = pre[i-1] + x;
    }
    for(int j=1; j<=k; j++){
        deque <line> lines;
        line nline;
        nline.a = pre[j];
        nline.b = -pre[j]*pre[j] + dpp[j];
        nline.ind = j;
        lines.push_back(nline);
        for(int i=j+1; i<=n; i++){
            while(lines.size() >= 2 && lines.front().eval(pre[i]) <= lines[1].eval(pre[i])){
                lines.pop_front();
            }
            dp[i] = lines.front().eval(pre[i]);
            prosli[j][i] = lines.front().ind;
            nline.a = pre[i];
            nline.b = -pre[i]*pre[i] + dpp[i];
            nline.ind = i;
            if(nline.a == lines.back().a){
                if(nline.b <= lines.back().b) continue;
                lines.pop_back();
                lines.push_back(nline);
            }
            else{
                while(lines.size() >= 2  && nline.intersect(lines.back()) <= lines.back().intersect(lines[lines.size()-2])){
                    lines.pop_back();
                }
                lines.push_back(nline);
            }
        }
        for(int i=1; i<=n; i++){
            dpp[i] = dp[i];
        }
    }
    cout << dp[n] << "\n";
    int t = n;
    for(int i=k; i>=1; i--){
        cout << prosli[i][t] << " ";
        t = prosli[i][t];
    }
    return 0;
}

/*
7 3
4 1 3 4 0 2 3
*/

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