Submission #1095244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095244		RaduM	Split the sequence (APIO14_sequence)	C++17	100 / 100	591 ms	100400 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int NMAX = 100005;
const int KMAX = 202;
int v[NMAX];
ll sp[NMAX];
ll dp[KMAX];
int last[NMAX][KMAX];

struct line{
    ll slope, yIntercept;
    line() {}
    line(ll slope, ll yIntercept) : slope(slope), yIntercept(yIntercept) {}

    ll val(int x){
        return slope * x + yIntercept;
    }

    ll intersect(const line &other){
        if(slope == other.slope) return 0;
        return (yIntercept - other.yIntercept + other.slope - slope - 1) / (other.slope - slope);
    }
};

struct CHT{
    deque < pair < pair <line, int>, int > > dq;

    void add(line l, int id){
        while(dq.size() > 1 && dq.back().first.second >= dq.back().first.first.intersect(l)) dq.pop_back();
        if(dq.empty()){
            dq.push_back({{l, 0}, id});
            return;
        }
        dq.push_back({{l, dq.back().first.first.intersect(l)}, id});
    }

    pair <int, ll> query(int x){
        while(dq.size() > 1){
            if(dq[1].first.second <= x) dq.pop_front();
            else break;
        }
        return {dq[0].second, dq[0].first.first.val(x)};
    }
};

CHT cht[KMAX];
vector <int> sol;

int main()
{
    int n,i,k,t;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for(i = 1; i <= n; i++){
        cin >> v[i];
        sp[i] = sp[i - 1] + v[i];
    }
    ll mx = 0;
    int poz = 1;
    for(i = 1; i < n; i++){
        dp[1] = sp[i] * (sp[n] - sp[i]);
        for(int e = 2; e <= min(k, i); e++){
            pair <int, ll> r = cht[e - 1].query(sp[i]);
            dp[e] = r.second + sp[i] * (sp[n] - sp[i]);
            last[i][e] = r.first;
        }
        for(int e = 1; e <= min(k, i); e++) cht[e].add(line(sp[i], dp[e] - sp[i] * sp[n]), i);
        if(dp[k] > mx){
            mx = dp[k];
            poz = i;
        }
    }
    sol.push_back(poz);
    while(k > 1){
        sol.push_back(last[poz][k]);
        poz = last[poz][k];
        k--;
    }
    cout << mx << "\n";
    for(auto x : sol) cout << x << " ";
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:54:15: warning: unused variable 't' [-Wunused-variable]
   54 |     int n,i,k,t;
      |               ^

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