Submission #1272291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272291		dragst	수열 (APIO14_sequence)	C++20	0 / 100	1 ms	336 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

long long dp[205][100005], dq[100005], a[100005], trace[205][100005];
stack<long long> st;

bool better(long long id, long long x, long long y, long long z) {return a[x]*z+dp[id][x]<=a[y]*z+dp[id][y];}

bool better2(long long id, long long x, long long y, long long z) {return (dp[id][x]-dp[id][y])*(a[z]-a[x])>=(dp[id][x]-dp[id][z])*(a[y]-a[x]);}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, k, i, j, l, r;
    cin >> n >> k;
    for (i=1; i<=n; i++)
    {
        cin >> a[i];
        a[i]+=a[i-1];
    };
    for (i=1; i<=k+1; i++)
    {
        l=r=1;
        dq[l]=0;
        for (j=1; j<=n; j++)
        {
            while (l<r && better(i-1, dq[l], dq[l+1], a[j]-a[n])) {l++;};
            dp[i][j]=a[dq[l]]*(a[j]-a[n])+dp[i-1][dq[l]]+a[n]*a[j]-a[j]*a[j];
            trace[i][j]=dq[l];
            while (r>l && better2(i-1, j, dq[r], dq[r-1])) {r--;};
            dq[++r]=j;
        };
    };
    cout << dp[k+1][n] << "\n";
    i=k+1; j=n;
    while (trace[i][j])
    {
        st.push(trace[i][j]);
        j=trace[i][j]; i--;
    };
    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    };
}

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