Submission #1272298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272298		dragst	수열 (APIO14_sequence)	C++20	100 / 100	330 ms	81860 KiB

sequence

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

long long dp[2][100005], a[100005];
int dq[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][z])*(a[z]-a[y])<=(dp[id][y]-dp[id][z])*(a[z]-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(1-i%2, dq[l], dq[l+1], a[j]-a[n])) {l++;};
            dp[i%2][j]=a[dq[l]]*(a[j]-a[n])+dp[1-i%2][dq[l]]+a[n]*a[j]-a[j]*a[j];
            trace[i][j]=dq[l];
            while (r>l && better2(1-i%2, j, dq[r], dq[r-1])) {r--;};
            dq[++r]=j;
        };
    };
    cout << dp[(k+1)%2][n] << "\n";
    i=k+1; j=n;
    while (i>1)
    {
        st.push(trace[i][j]);
        j=trace[i][j]; i--;
    };
    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    };
}

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