Submission #539350

#	Time	Username	Problem	Language	Result	Execution time	Memory
539350		vector	Split the sequence (APIO14_sequence)	C++17	78 / 100	947 ms	84308 KiB

sequence

#include<bits/stdc++.h>
#define SIZE 100001
using namespace std;
typedef long long ll;
struct line
{
    ll a,b;
};
ll A[SIZE],dp[SIZE][2],psum[SIZE];
int N,K,idx[SIZE][201],sw;
vector<line>v;
double cross(line x,line y)
{
    return (double)(y.b-x.b)/(psum[x.a]-psum[y.a]);
}
void ins(line x)
{
    if(!v.empty()&&psum[v.back().a]==psum[x.a]){
        if(v.back().b<x.b)v.back().b=x.b;
        return;
    }
    while(v.size()>=2){
        if(cross(v.back(),v[v.size()-2])>cross(v.back(),x))v.pop_back();
        else break;
    }
    v.push_back(x);
}
pair<ll,ll>query(ll x)
{
    if(v.size()<=sw)sw=v.size()-1;
    while(sw+1<v.size()&&cross(v[sw+1],v[sw])<=x)sw++;
    return {psum[v[sw].a]*x+v[sw].b,v[sw].a};
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin>>N>>K;
    for(int i=1;i<=N;i++){
        cin>>A[i];
        psum[i]=psum[i-1]+A[i];
        ins({i,-psum[i]*psum[i]});
    }
    for(int i=1;i<=K;i++){
        sw=0;
        for(int j=i+1;j<=N;j++){
            pair<ll,ll>t=query(psum[j]);
            dp[j][1]=t.first;
            idx[j][i]=t.second;
        }
        v.clear();
        for(int j=i+1;j<=N;j++){
            ins({j,dp[j][1]-psum[j]*psum[j]});
            dp[j][0]=dp[j][1];
        }
    }
    vector<int>ans;
    int x=N;
    for(int i=K;i>=1;i--){
        ans.push_back(idx[x][i]);
        x=idx[x][i];
    }
    printf("%lld\n",dp[N][1]);
    for(int i=ans.size()-1;i>=0;i--)printf("%d ",ans[i]);
}

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, long long int> query(ll)':
sequence.cpp:30:16: warning: comparison of integer expressions of different signedness: 'std::vector<line>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |     if(v.size()<=sw)sw=v.size()-1;
      |        ~~~~~~~~^~~~
sequence.cpp:31:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     while(sw+1<v.size()&&cross(v[sw+1],v[sw])<=x)sw++;
      |           ~~~~^~~~~~~~~

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