Submission #705307

#	Time	Username	Problem	Language	Result	Execution time	Memory
705307		speedyArda	Split the sequence (APIO14_sequence)	C++14	100 / 100	1334 ms	84172 KiB

sequence

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
//ll dp[MAXN][205];
vector<ll> new_dp(MAXN), dp(MAXN);
ll in[MAXN], pref[MAXN];
int cut[MAXN][205];
ll n, k;


void solve(int l, int r, int optl, int optr, int k)
{
    if(l > r)
        return;
    int mid = (l + r) / 2;
    pair<ll, ll> best = {-1e18, -1};
    for(int i = optl; i <= min(mid, optr); i++)
    {
        best = max(best, {dp[i-1] + (pref[mid] - pref[i - 1]) * (pref[n] - pref[mid]), i});
    }
    new_dp[mid] = best.first;
    int opt = best.second;
    cut[mid][k] = opt;
    solve(l, mid - 1, optl, opt, k);
    solve(mid + 1, r, opt, optr, k); // From the monotonicity: opt(i, j) <= opt(i, j + 1); in which case opt is our point where we split our l, r range to get the sum most valuable. Since right side of the sum increase as we increase j, so opt side will also increase/stay the same compared with a lower j (to balance the sum between left side and right side) so opt(i, j) <= opt(i, j + 1) holds.
}

int main() 
{
    //ll n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> in[i];
        pref[i] = pref[i - 1] + in[i];
        //dp[i][0] = pref[i];
    }

    for(int i = 1; i <= k; i++) 
    {
        solve(1, n-1, 1, n-1, i);
        dp = new_dp;
    }

    ll ans = 0;
    int curr = 0;
    for(int i = 1; i <= n - 1; i++) {
        ans = max(ans, dp[i]); // dp[i][k] maximum points by last splitting a range which ends with i.
        if(ans == dp[i])
            curr = i;
    }
    cout << ans << "\n";
    vector<int> moves;
    moves.push_back(curr);
    for(int i = k; i > 1; i--)
    {
        moves.push_back(cut[curr][i] - 1);
        curr = cut[curr][i] - 1;

    }
    reverse(moves.begin(), moves.end());
    for(int e : moves)
        cout << e << " ";
    cout << "\n";
}

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