Submission #752817

#	Time	Username	Problem	Language	Result	Execution time	Memory
752817		winter0101	Split the sequence (APIO14_sequence)	C++14	100 / 100	932 ms	83440 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=1e5+9;
long long a[maxn];
long long dp[maxn][2];
int trace[maxn][202];
struct line {
long long x,y;
};
long double intersect(const line &p,const line &q){
return (1.0*(1.0*(q.y-p.y))/(1.0*(p.x-q.x)));
}
bool check(const line &p, const line &q, const line &r){
return (intersect(p,q)>=intersect(p,r));
}
long long cal(const line &p,const long long val){
return p.x*val+p.y;
}
struct cht{
deque<pair<line,int>>c;
void add(const line &p,int id){
if (c.empty()){
  c.pb({p,id});
  return;
}
while (!c.empty()&&c.back().fi.x==p.x&&c.back().fi.y<p.y)c.pop_back();
if (!c.empty()&&c.back().fi.x==p.x&&c.back().fi.y>=p.y)return;
while(sz(c)>=2&&check(c[sz(c)-2].fi,c[sz(c)-1].fi,p))c.pop_back();
c.pb({p,id});
}
pair<long long,int> query(long long val){
while (sz(c)>=2&&cal(c[0].fi,val)<=cal(c[1].fi,val))c.pop_front();
return {cal(c[0].fi,val),c[0].se};
}
};
signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    int n,k;
    cin>>n>>k;
    for1(i,1,n){
    cin>>a[i];
    a[i]+=a[i-1];
    }
    k++;
    for1(j,2,k){
    cht temp;
    line tem;
    tem.x=a[j-1];
    tem.y=dp[j-1][0]-a[j-1]*a[j-1];
    temp.add(tem,j-1);
    for1(i,j,n){
    pair<long long,int>wait=temp.query(a[i]);
    trace[i][j]=wait.se;
    dp[i][1]=wait.fi;
    tem.x=a[i];
    tem.y=dp[i][0]-a[i]*a[i];
    temp.add(tem,i);
    }
    for1(i,j,n){
    dp[i][0]=dp[i][1];
    dp[i][1]=0;
    }
    }
    cout<<dp[n][0]<<'\n';
    vector<int>cc;
    cc.pb(n);
    while (sz(cc)<k){
        cc.pb(trace[cc.back()][k+1-sz(cc)]);
    }
    //cout<<trace[7][4]<<'\n';
    reverse(all(cc));
    cc.pop_back();
    for (auto v:cc){
        cout<<v<<" ";
    }


}

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