Submission #585478

#	Time	Username	Problem	Language	Result	Execution time	Memory
585478		socpite	Split the sequence (APIO14_sequence)	C++17	100 / 100	1448 ms	92336 KiB

sequence

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

#define f first
#define s second

typedef long long ll;

const int maxn = 1e5+5;
const int maxk = 205;

int n, k;
ll dp[maxn][2], A[maxn];
int ans[maxn];
int trace[maxn][maxk];

int md= 1;

struct pt{
    ll x, y;
    int id;
    pt(){};
    pt(ll a, ll b, int c = 0){
        x = a;
        y = b;
        id = c;
    }
    pt rt(){
        return pt(-y, x);
    }
    pt operator-(pt b){
        return pt(x-b.x, y-b.y);
    }
};

ll dot(pt a, pt b){
    return a.x*b.x + a.y*b.y;
}

ll cross(pt a, pt b){
    return a.x*b.y - a.y*b.x;
}

struct cvh{
    int r= 0 ;
    vector<pt> vecs;
    vector<pt> hull;
    void add(pt nw){
        while(!vecs.empty() && dot(vecs.back(), nw-hull.back()) >= 0){
            vecs.pop_back();
            hull.pop_back();
        }
        if(!hull.empty()){
            vecs.push_back((nw-hull.back()).rt());
        }
        hull.push_back(nw);
    }
    pair<int, ll> query(ll nw){
        r = min(r, int(vecs.size()));
        while(r < vecs.size() && cross(vecs[r], pt(nw, 1)) < 0)r++;
        return {hull[r].id, dot(pt(nw, 1), hull[r])};
    }
};

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> A[i];
        A[i]+=A[i-1];
    }
    for(int i = 1; i <= k; i++){
        cvh sus;
        sus.add(pt(0, 0));
        for(int j = 1; j <= n; j++){
            auto tmp = sus.query(A[j]);
            dp[j][1]=tmp.s;
            trace[j][i]=tmp.f;
            sus.add(pt(A[j], dp[j][0] - A[j]*A[j], j));
        }
        for(int j = 1; j <= n; j++)dp[j][0]=dp[j][1];
    }
    cout << dp[n][0] << "\n";
    int r = n;
    for(int i = k; i > 0; i--){
        r = trace[r][i];
        ans[i]=r;
    }
    for(int i = 1; i <= k; i++){
        if(ans[i] <= ans[i-1])ans[i]=ans[i-1]+1;
        cout << ans[i] << " ";
    }
}

Compilation message (stderr)

sequence.cpp: In member function 'std::pair<int, long long int> cvh::query(ll)':
sequence.cpp:60:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         while(r < vecs.size() && cross(vecs[r], pt(nw, 1)) < 0)r++;
      |               ~~^~~~~~~~~~~~~

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