Submission #989439

#	Time	Username	Problem	Language	Result	Execution time	Memory
989439		coldbr3w	Split the sequence (APIO14_sequence)	C++17	0 / 100	69 ms	131072 KiB

sequence

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

using ll = int;
using pll = pair<int, int>;

#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 1e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 520;
const ll base = 35711;
ll n,k;
ll a[N], mp[N], dp[N], lst[N], ps[N];
pll trace[N][210];
void compute(ll l, ll r, ll optl, ll optr, ll turn){
    if(l > r) return;
    ll mid = (l + r) / 2;
    pll res = {-inf, -1};
    for(int i = optl; i <= min(mid, optr);i++){
        res = max(res, {lst[i - 1] + (ps[mid] - ps[i - 1]) * (ps[i-1]), i});
    }
    trace[mid][turn] = {res.S - 1, turn - 1};
    dp[mid] = res.F;
    ll opt = res.S;
    compute(l, mid - 1, optl, opt, turn); 
    compute(mid + 1, r, opt, optr, turn);
}
/*
7 3
4 1 3 4 0 2 3
*/
void to_nho_cau(){
    cin >> n >> k;
    for(int i = 1; i <= n;i++){
        cin >> a[i];
        ps[i] = ps[i-1] + a[i];
    }
    for(int j = 1; j <= k;j++){
        compute(1, n, 1, n, j);
        for(int i = 0; i <= n;i++) lst[i] = dp[i], dp[i] = 0;
    }
    cout << lst[n] << '\n';
    ll i = n, j = k;
    while(j >= 1){
        ll nxt_i = trace[i][j].F, nxt_j = trace[i][j].S;
        i = nxt_i, j = nxt_j;
        if(i >= 1) cout << i << ' ';
    }
    cout << '\n';
}

signed main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;   
    //cin >> t;
    while(t--) to_nho_cau();
}

Compilation message (stderr)

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

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