Submission #329241

#	Time	Username	Problem	Language	Result	Execution time	Memory
329241		jovan_b	Split the sequence (APIO14_sequence)	C++17	62 / 100	444 ms	81592 KiB

sequence

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

typedef long long ll;

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;
    }
};

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;
    }
    line dummy_line;
    dummy_line.a = 0;
    dummy_line.b = -2000000000000000000LL;
    dummy_line.ind = 0;
    for(int j=1; j<=k; j++){
        deque <line> lines;
        lines.push_back(dummy_line);
        for(int i=1; i<=n; i++){
            while(lines.size() >= 2){
                line line1 = lines.front();
                lines.pop_front();
                line line2 = lines.front();
                if(line2.eval(pre[i]) < line1.eval(pre[i])){
                    lines.push_front(line1);
                    break;
                }
            }
            dp[i] = lines.front().eval(pre[i]);
            prosli[j][i] = lines.front().ind;
            line nline;
            nline.a = pre[i];
            nline.b = -pre[i]*pre[i] + dpp[i];
            nline.ind = i;
            if(pre[i]-pre[i-1] || nline.b > lines.back().b) 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: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 29 / 29