Submission #1058254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058254		codefox	Split the sequence (APIO14_sequence)	C++14	100 / 100	595 ms	86860 KiB

sequence

#include<bits/stdc++.h>
    
using namespace std;
    
#define ll long long
    
#pragma GCC optimize("O3,fast-math")

const int N = 1e5+1;
const int K = 202;
    
ll dp[N][2];
ll pref[N];
int best[N][K];

double inter2(int &i, int &j)
{
    return ((-pref[j]*pref[j]+dp[j][0])-(-pref[i]*pref[i]+dp[i][0]))/(double)(pref[i]-pref[j]);
}
    
ll inter(int &i, int &j)
{
    return ((-pref[j]*pref[j]+dp[j][1])-(-pref[i]*pref[i]+dp[i][1]));
}
    
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("../input.txt", "r", stdin);
    //freopen("../output.txt", "w", stdout);
    
    int n, k;
    cin >> n >> k;
    k++;
    deque<int> ch[K];
    ch[0].push_back(0);

    pref[0] = 0;
    dp[0][0] =0;

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

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