Submission #1185118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185118		boxfish	Split the sequence (APIO14_sequence)	C++20	0 / 100	1 ms	324 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

struct line{
    ll m, c, id;
    ll eval(ll x){return m * x + c;}
    ld inter(line l){return (long double)(c - l.c) / (l.m - m);}
};
int n, k;
ll a[100005], dp[100005][2], pre[1000005], race[100005][205];
deque<ll> dq;

bool bad(ll m1, ll b1, ll m2, ll b2, ll m3, ll b3){
    return (m2 - b2) * (m1 - b1) >= (m3 - b3) * (m2 - b2);
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n ; ++i){
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    for(int i = 1 ; i <= n ; ++i)
        dp[i][0] = pre[i] * (pre[n] - pre[i]);
    for(int i = 1; i <= k ; ++i){
        dq.clear();
        for(int j = i + 1 ; j <= n ; ++j){
            ll suf = pre[n] - pre[j];
            while((int)dq.size() >= 2){
                ll s1 = dq.back(), s2 = dq[dq.size() - 2];
                if(bad(-pre[s1],dp[s1][0],-pre[s2],dp[s2][0],-pre[j - 1],dp[j - 1][0]))
                    dq.pop_back();
                else break;
            }
            dq.push_back(j - 1);
            while((int)dq.size() >= 2){
                ll s1 = dq[0];
                ll s2 = dq[1];
                s1 = dp[s1][0] + (pre[j] - pre[s1]) * suf;
                s2 = dp[s2][0] + (pre[j] - pre[s2]) * suf;
                if(s1 <= s2) dq.pop_front();
                else break;
            }
            ll val = dp[dq[0]][0] + (pre[j] - pre[dq[0]]) * suf;
            dp[j][1] = val;
            race[j][i] = dq[0];


        }
        for(int j = i + 1 ; j <= n ; ++j)
            dp[j][0] = dp[j][1];
    }
    ll res = dp[n][1];
    vector<int> v;
    int pos = n;
    for(int i = k ; i >= 1;  --i){
        pos = race[pos][i];
        v.push_back(pos);
    }
    reverse(v.begin(),v.end());
    cout << res << '\n';
    for(int i : v) cout << i << ' ';
    return 0;
}

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