Submission #1098951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098951		raul2008487	Split the sequence (APIO14_sequence)	C++17	100 / 100	569 ms	81748 KiB

sequence

#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define in insert
#define fi first
#define se second
#define vl vector<ll>
#define all(v) v.begin(), v.end()
#define endl "\n"

using namespace std;
const int sz = 1e5 + 123; /// mind this
const int MAX = 2e6 + 123;
const int BS = 61;
const ll inf = 1e17;
long long dp[2][sz], p[sz];
ll part[205][sz], n;
bool cmp1(ll x, ll y, ll i){
    long long canx = dp[0][x] + (p[i] - p[x]) * (p[n] - p[i]);
    long long cany = dp[0][y] + (p[i] - p[y]) * (p[n] - p[i]);
    return (canx <= cany);
}
bool cmp2(ll x, ll y, ll i){
    long long c1 = (dp[0][y] - dp[0][x]) * (p[i] - p[y]);
    long long c2 = (dp[0][i] - dp[0][y]) * (p[y] - p[x]);
    return (c1 <= c2);
}
void solve(){
    ll k, i, j;
    cin >> n >> k;
    vl v(n + 1);
    for(i = 1; i <= n; i++){
        cin >> v[i];
        p[i] = p[i - 1] + v[i];
    }
    deque<ll> dq;
    for(i = 1; i <= k; i++){
        dq.pb(0);
        for(j = 1; j <= n; j++){
            while(dq.size() > 1 && cmp1(dq[0], dq[1], j)){
                dq.pop_front();
            }
            ll cut = dq.front();
            dp[1][j] = dp[0][cut] + (p[j] - p[cut]) * (p[n] - p[j]);
            // cout << j << ' ' << cut << ' ' << dp[1][j] << endl;
            part[i][j] = cut;
            while(dq.size() > 1 && cmp2(dq[dq.size() - 2], dq.back(), j)){
                dq.pop_back();
            }
            dq.pb(j);
        }
        dq.clear();
        for(j = 1; j <= n; j++){
            dp[0][j] = dp[1][j];
        }
    }
    long long ans = -1, idx = -1;
    for(i = 1; i <= n; i++){
        if(dp[0][i] > ans){
            ans = dp[0][i], idx = i;
        }
    }
    cout << ans << endl;
    for(i = k; i > 0; i--){
        assert(idx >= 0 && idx <= n);
        cout << idx << ' ';
        idx = part[i][idx];
    }
    cout << endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

sequence.cpp:16:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   16 | const ll inf = 1e17;
      |                ^~~~

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