Submission #569583

#	Time	Username	Problem	Language	Result	Execution time	Memory
569583		Ronin13	Split the sequence (APIO14_sequence)	C++14	71 / 100	762 ms	131072 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const ll linf = 1e18 + 1;

struct ftype{
    ll k, b, ind;
    ftype(ll k, ll b, ll ind) : k(k), b(b), ind(ind){
    }
    ftype(){
        k = -1000;
        b = ind = -linf;
    }
    ll get(ll x){
        return k * x + b;
    }
};

vector <ftype> t(400001);

vector <ll> suf;
map<int, int> mp;
bool comp(ftype a, ftype b, ll x){
    return a.get(suf[x - 1]) > b.get(suf[x - 1]);
}

void addline(int v, ll l, ll r, ftype nw){
    ll m = (l + r) / 2;
    bool f1 = comp(nw, t[v], l);
    bool f2 = comp(nw, t[v], m);
    if(f2) swap(t[v], nw);
    if(l == r) return;
    if(f1 != f2){
        addline(2 * v, l, m, nw);
    }
    else{
        addline(2 * v + 1, m + 1, r, nw);
    }
}

ftype query(int v, ll l, ll r, ll x){
    if(l == r) return t[v];
    ll m= (l + r) / 2;
    if(x <= m){
        ftype nw = query(2 * v, l, m, x);
        if(nw.get(suf[x - 1]) > t[v].get(suf[x - 1])) return nw;
        return t[v];
    }
    ftype nw = query(v * 2 + 1, m + 1, r, x);
    if(nw.get(suf[x - 1]) > t[v].get(suf[x - 1])) return nw;
    return t[v];
}

ll dp[100001][201];
ll p[100001][201];

int main(){
    int n, k; cin >> n >> k;
    ll a[n + 1];
    ll pref[n + 1];
    pref[0] = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }
    for(int i = 0; i <= n; i++){
        suf.pb(pref[n] - pref[i]);
    }
    int L = 1, R = n;
    sort(suf.begin(), suf.end());
    for(int i = 0; i < suf.size(); i++){
        mp[suf[i]] = i + 1;
    }
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= k; j++) dp[i][j] = -linf;
    }
    dp[0][0] = 0;
    for(int i = 1; i <= k; i++){
        for(int j = 1; j <= 4 * n; j++){
            t[j].k = -10;
            t[j].b = -linf;
            t[j].ind = -1;
        }
        t.pb({-10, -linf, -1});
        t.pb({-10, -linf, -1});
        addline(1, L, R, {0, dp[0][i - 1], 0});
        for(int j = 1; j <= n; j++){
            ll x = pref[n] - pref[j];
            x = mp[x];
            ftype res = query(1, L, R, x);
            dp[j][i] = max(pref[j] * (pref[n] - pref[j]) + res.get(suf[x - 1]), dp[j][i]);
            p[j][i] = res.ind;
            addline(1, L, R, {-pref[j], dp[j][i - 1], j});
        }
    }
    ll ans = -1;
    int ansi;
    for(int i = 1; i <= n; i++){
        if(dp[i][k] > ans) ans = dp[i][k], ansi = i;
    }
    cout << ans << "\n";
    int cnt = k;
    vector <int> vec;
    while(cnt){
        vec.pb(ansi);
        ansi = p[ansi][cnt--];
    }
    reverse(vec.begin(), vec.end());
    for(int to : vec) cout << to << ' ';
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0; i < suf.size(); i++){
      |                    ~~^~~~~~~~~~~~

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