제출 #705305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705305		speedyArda	수열 (APIO14_sequence)	C++14	60 / 100	97 ms	131072 KiB

sequence

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
ll dp[MAXN][205];
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][k-1] + (pref[mid] - pref[i - 1]) * (pref[n] - pref[mid]), i});
    }
    dp[mid][k] = 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);
    }

    /*for(int l = 1; l <= n; l++)
    {
        for(int r = l; r <= n; r++)
        {
            cout << l << " " << r << " " << point(l, r) << "\n";
        }
    }*/

    ll ans = 0;
    int curr = 0;
    for(int i = 1; i <= n; i++) {
        ans = max(ans, dp[i][k]); // dp[i][k] maximum points by last splitting a range which ends with i.
        if(ans == dp[i][k])
            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: 0 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29