제출 #569559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569559		Ronin13	수열 (APIO14_sequence)	C++14	71 / 100	1026 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 = b = ind = 0;
    }
    ll get(ll x){
        return k * x + b;
    }
};

vector <ftype> t;
vector <int> le, ri;
ll L = 0, R = 1e9 + 1;

bool comp(ftype a, ftype b, ll x){
    return a.get(x) > b.get(x);
}

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){
        int x = le[v];
        if(x == 0){
            le[v] = t.size();
            t.pb(nw);
            le.pb(0);
            ri.pb(0);
        }
        addline(le[v], l, m, nw);
    }
    else{
        int x = ri[v];
        if(x == 0){
            ri[v] = t.size();
            t.pb(nw);
            le.pb(0);
            ri.pb(0);
        }
        addline(ri[v], m + 1, r, nw);
    }
}

ftype query(int v, int l, int r, ll x){
    if(l == r) return t[v];
    int m = (l + r) / 2;
    if(x <= m){
        if(le[v] == 0) {
            return t[v];
        }
        ftype nw = query(le[v], l, m, x);
        if(nw.get(x) > t[v].get(x)) return nw;
        return t[v];
    }
    if(ri[v] == 0) {
        return t[v];
    }
    ftype nw = query(ri[v], m + 1, r, x);
    if(nw.get(x) > t[v].get(x)) 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++){
        for(int j = 0; j <= k; j++) dp[i][j] = -linf;
    }
    dp[0][0] = 0;
    for(int i = 1; i <= k; i++){
        t.clear();
        le.clear();
        ri.clear();
        t.pb({-10, -linf, -1});
        t.pb({-10, -linf, -1});
        le.pb(0);
        le.pb(0);
        ri.pb(0);
        ri.pb(0);
        addline(1, L, R, {0, dp[0][i - 1], 0});
        for(int j = 1; j <= n; j++){
            ll x = pref[n] - pref[j];
            ftype res = query(1, L, R, x);
            dp[j][i] = max(pref[j] * x + res.get(pref[n] - pref[j]), 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;
}

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