제출 #705304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705304		speedyArda	수열 (APIO14_sequence)	C++14	0 / 100	82 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;
ll point(ll tl, ll tr)
{

    ll ans = 0, l = tl, r = tr;
    while(l <= r)
    {
        ll m = (l + r) / 2;
        ans = max(ans, (pref[m] - pref[tl-1]) * (pref[tr] - pref[m]));
        if(pref[m] - pref[tl - 1] > pref[tr] - pref[m]) // Trying to find the position where the difference between sum of two sides is minimal.
            r = m - 1;
        else
            l = m + 1;
    }
    ans = max(ans, (pref[l] - pref[tl-1]) * (pref[tr] - pref[l]));
    ans = max(ans, (pref[l+1] - pref[tl-1]) * (pref[tr] - pref[l+1]));
    return ans;
}

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, n, 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;
    curr = cut[curr][k];
    for(int i = k-1; i >= 0; i--)
    {
        moves.push_back(curr);
        curr = cut[curr][i];

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

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