Submission #1260621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260621		KawakiMeido	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	328 KiB

sequence

/*Author: KawakiMeido*/
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define ll long long
#define int long long
#define ld long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;

/*Constants*/
const int N = 1e5+10;
const int INF = 1e9+7;
const long long LLINF = 1e18+3;

/*TestCases*/
int test=1;
void solve();
void TestCases(bool v){
    if (v) cin >> test;
    while(test--) solve();
}

/*Global Variables*/
int n,k;
int a[N],pre[N];
pii dp[205][N];

struct Line{
    ll m,n;

    Line (ll _m=0, ll _n=0): m(_m), n(_n){};

    ll operator()(ll x) const{return m*x+n;}

    bool operator== (Line line) const {return (m==line.m && n==line.n);}

    friend ld intersect(Line a, Line b) {return (ld)(b.n-a.n)/(ld)(a.m-b.m);};
};

/*Solution*/
void solve(){
    cin >> n >> k;
    for (int i=1; i<=n; i++){
        cin >> a[i];
    }

    for (int i=1; i<=n; i++){
        pre[i] = pre[i-1] + a[i];
    }

    deque<pair<Line,int>> dq;

//    cout << 1/0 << endl;

    for (int j=1; j<=k; j++){
        dq.clear();
        dq.push_back({Line(pre[j-1],dp[j-1][j-1].fi-pre[j-1]*pre[j-1]),j-1});
        for (int i=j; i<=n; i++){
            while (dq.size() > 1 && intersect(dq[0].fi,dq[1].fi) < pre[i]) dq.pop_front();
//            cout << i << " " << j << " " << dq.size() << endl;
            dp[j][i].fi = dq[0].fi(pre[i]);
            dp[j][i].se = dq[0].se;
            Line line(pre[i],dp[j-1][i].fi-pre[i]*pre[i]);
            if (j>1){
                while (dq.size() > 1 && (dq[dq.size()-1].fi==line || intersect(dq[dq.size()-1].fi,dq[dq.size()-2].fi) > intersect(dq[dq.size()-1].fi,line))) dq.pop_back();
                dq.push_back({line,i});
            }
        }
    }
    ll ans = -1;
    int pos = 0;
    for (int i=k; i<n; i++){
        if (ans < dp[k][i].fi + (pre[n] - pre[i])*pre[i]){
            ans = max(ans,dp[k][i].fi + (pre[n] - pre[i])*pre[i]);
            pos = i;
        }
    }
    cout << ans << endl;
    for (int i=k; i>0; i--){
        cout << pos << " ";
        pos = dp[i][pos].se;
    }
}

/*Driver Code*/
signed main(){
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);
//    freopen("sequence.in","r",stdin);
//    freopen("sequence.out","w",stdout);

    TestCases(0);

    return 0;
}

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