Submission #989524

#	Time	Username	Problem	Language	Result	Execution time	Memory
989524		reginox	Split the sequence (APIO14_sequence)	C++17	100 / 100	626 ms	85076 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define all(v) begin(v), end(v)
#define pi pair<ll, ll>
#define vi vector<ll>
#define task "test"
using namespace std;
const ll maxn = 1e5+3;
ll n, k, a[maxn], tl=1, tr=0, dp[maxn][2], pf[maxn], sq[maxn];
int trace[maxn][205];
ll x, cnt[maxn];
vector<ll> ans;

ll cost(ll l, ll r){
    return (pf[r] - pf[l-1])*pf[l-1];
}

void cmp(ll l, ll r, ll optl, ll optr, ll cur){
    if(l > r) return ;
    ll mid = (l+r)>>1, id = -1, mx = -1e18, v;
    for(ll i = optl; i <= min(mid, optr); i++){
        v = dp[i-1][0] + cost(i, mid);
        if(v >= mx){
            mx = v, id = i;
        }
    }
    // cerr << l << " " << r << " " << mx << "\n";
    dp[mid][1] = mx;
    trace[mid][cur] = id;
    if(l == r) return ;
    cmp(l, mid-1, optl, id, cur);
    cmp(mid+1, r, id, optr, cur);
}

int main(){
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    k++;
    for(ll i = 1; i <= n; i++){
        cin >> a[i];
        pf[i] = pf[i-1] + a[i];
        sq[i] = sq[i-1] + a[i]*a[i];
    }
    for(ll j = 2; j <= k; j++){
        cmp(1, n, 1, n, j);
        for(ll i = 1; i <= n; i++) dp[i][0] = dp[i][1];
        // cout << "\n";
        // for(ll i = 1; i <= n; i++) cout << dp[i][0] << " ";
    }
    cout << dp[n][0] << "\n";
    // for(ll j = 1; j <= k; j++){
    //     for(ll i = 1; i <= n; i++) cout << trace[i][j] << " ";
    //     cout << "\n";
    // }
    ll pt = n;
    for(ll i = k; i >= 2; i--){
        ans.push_back(trace[pt][i]-1);
        pt = trace[pt][i]-1;
    }
    reverse(all(ans));
    for(auto x:ans) cout << x << " ";
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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