Submission #890608

#	Time	Username	Problem	Language	Result	Execution time	Memory
890608		dwuy	Split the sequence (APIO14_sequence)	C++14	100 / 100	825 ms	87736 KiB

sequence

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int MX = 100005;
int n, k;
int a[MX];
int sum[MX];
int pre[MX];
int cur[MX];
int32_t trace[MX][205];

void nhap(){
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];
}

vector<pii> Line;
vector<int> id;

/// ax + b = ux + v;
/// ax - ux = v - b;
/// x(a - u) = (v - b)
/// x = (v - b)/(a - u);
bool bad(pii l1, pii l2, pii l3){
    return (l2.se - l1.se)*(l2.fi - l3.fi) >= (l1.fi - l2.fi)*(l3.se - l2.se);
}

void addLine(pii cur, int idx){
    while(Line.size() > 1 && bad(cur, Line.back(), Line[Line.size()-2])){
        Line.pop_back();
        id.pop_back();
    }
    Line.push_back(cur);
    id.push_back(idx);
}

pii get(int x){
    int res = (int)Line.size() - 1;
    for(int lo=0, hi=(int)Line.size()-2; lo<=hi;){
        int mid = (lo+hi)>>1;
        if(x*(Line[mid].fi - Line[mid+1].fi)>=(Line[mid+1].se - Line[mid].se)) res = mid, hi = mid - 1;
        else lo = mid + 1;
    }
    return {Line[res].fi*x + Line[res].se, id[res]};
}

void solve(){
    for(int i=1; i<=n; i++) sum[i] = sum[i-1] + a[i];
    for(int i=1; i<=n; i++) pre[i] = sum[i]*(sum[n] - sum[i]);
    for(int j=2; j<=k; j++){
        Line.clear();
        id.clear();
        addLine({-sum[j-1], pre[j-1]}, j-1);
        for(int i=j; i<=n; i++){
            pii tmp = get(sum[n] - sum[i]);
            cur[i] = tmp.fi + sum[i]*(sum[n] - sum[i]);
            trace[i][j] = tmp.se;
            addLine({-sum[i], pre[i]}, i);
        }
        for(int i=1; i<=n; i++) pre[i] = cur[i], cur[i] = 0;
    }
    pii ans = {-1, 0};
    for(int i=1; i<n; i++) ans = max(ans, {pre[i], i});
    vector<int> path;
    for(int u=ans.se, t=k; u!=0; u=trace[u][t], t--) path.push_back(u);
    cout << ans.fi << endl;
    reverse(path.begin(), path.end());
    for(int &x: path) cout << x << ' ';
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    nhap();
    solve();

    return 0;
}

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