Submission #1057982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057982		codefox	Split the sequence (APIO14_sequence)	C++14	0 / 100	37 ms	17116 KiB

sequence

#include<bits/stdc++.h>

using namespace std;

vector<vector<int>> dp;
vector<int> pref;

int inter(int i, int j, int k)
{
    return ((-pref[j]*pref[j]+dp[j][k])-(-pref[i]*pref[i]+dp[i][k]))/(double)(pref[i]-pref[j]);
}

int main()
{
    //freopen("../input.txt", "r", stdin);
    //freopen("../output.txt", "w", stdout);

    int n, k;
    cin >> n >> k;
    k++;
    vector<deque<int>> ch(k+1);
    ch[0].push_back(0);

    pref.assign(n+1, 0);
    dp.assign(n+1, vector<int>(k+1, 0));
    vector<vector<int>> best(n+1, vector<int>(k+1, -1));
    for (int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        pref[i] = pref[i-1];
        pref[i]+=a;
        for(int j = min(k-1, i-1); j>= 0; j--)
        {
            while (ch[j].size()>1 && inter(ch[j][0], ch[j][1], j)<=pref[i]) ch[j].pop_front();
            int h = ch[j].front();
            best[i][j+1] = h;
            dp[i][j+1] = dp[h][j]-pref[h]*pref[h]+pref[i]*pref[h];
            while (ch[j+1].size()>1 && inter(ch[j+1].back(), ch[j+1][ch[j+1].size()-2], j+1)>= inter(ch[j+1].back(), i, j+1)) ch[j+1].pop_back();
            ch[j+1].push_back(i);
        }
    }
    int cn = n;
    cout << dp[cn][k] << "\n";
    for (int i = k; i >= 2; i--)
    {
        cout << best[cn][i] << " ";
        cn = best[cn][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