Submission #283338

#	Time	Username	Problem	Language	Result	Execution time	Memory
283338		laoriu	Split the sequence (APIO14_sequence)	C++14	0 / 100	108 ms	131076 KiB

sequence

#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAX=100005,MAX2=203,inf=1e18;
//typedef pair < ii , int > iii;

using ll = long long;
using ld = long double;
int n;
int a[MAX];
int f[MAX][MAX2];
using ps=pair < int , int >;
using line =pair < int , int >;
ps ii( int a,int b){
    if(b<0) return ps(-a,-b);
    else return ps(a,b);
}
bool cmp(ps a, ps b){
    return ld(1)*a.X*b.Y<ld(1)*a.Y*b.X;
}
bool ss(ps a,int b){
    return ld(1)*a.X<=ld(1)*b*a.Y;
}
ps giao (line a,line b){
    return ii(b.Y-a.Y,a.X-b.X);
}
vector < line > pr[MAX2];
vector < ps > ad[MAX2];
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("sequence.inp","r",stdin);//freopen("sequence.out","w",stdout);
    int m;
    cin>>n>>m;
    m++;
    ///dp[i][k]=dp[j][k-1]+a[j]*(a[i]-a[j]);
    for(int i=1;i<=m;i++){

        cin>>a[i];a[i]+=a[i-1];

        f[i][i]=f[i-1][i-1]+a[i-1]*(a[i]-a[i-1]);
        ad[i].pb(ii(-inf,1));
        pr[i].pb(line(a[i],f[i][i]-a[i]*a[i]));
        line now;
        for(int j=i-1;j>1;j--){
            int b=0,e=ad[j-1].size()-1,an;
            while(b<=e){
                int mi=b+e>>1;
                if(ss(ad[j-1][mi],a[i])){

                   b=mi+1;an=mi;
                }
                else e=mi-1;
            }
            now=pr[j-1][an];
            f[i][j]=now.X*a[i]+now.Y;
            //cout<<an<<' '<<i<<' '<<j<<' '<<now.X<<' '<<now.Y<<' '<<a[i]<<' '<<f[i][j]<<'\n';
            now=line(a[i],f[i][j]-a[i]*a[i]);

            ps x;
            while(pr[j].size()>1){
                x=giao(pr[j].back(),now);
                if((x.Y==0 && now.Y>=pr[j].back().Y) || cmp(x,ad[j].back())){
                    pr[j].pop_back();ad[j].pop_back();
                }
                else break;
            }
            x=giao(pr[j].back(),now);

            pr[j].pb(now);
            ad[j].pb(x);
        }

            if(i!=1){
                now=line(a[i],-a[i]*a[i]);
                ps x;
                while(pr[1].size()>1){
                    x=giao(pr[1].back(),now);
                    if((x.Y==0 && now.Y>=pr[1].back().Y) || cmp(x,ad[1].back())){
                        pr[1].pop_back();ad[1].pop_back();
                    }
                    else break;
                }
                x=giao(pr[1].back(),now);
                pr[1].pb(now);
                ad[1].pb(x);
            }
    }
    //return 0;
    for(int i=m+1;i<=n;i++){
        //cerr<<i;
        cin>>a[i];a[i]+=a[i-1];
        line now;
        for(int j=m;j>1;j--){
            int b=0,e=ad[j-1].size()-1,an;

            while(b<=e){
                int mi=b+e>>1;
                //if(i==10) cout<<ad[j-1][mi].X<<' '<<ad[j-1][mi].Y<<'\n';
                if(ss(ad[j-1][mi],a[i])){

                   b=mi+1;an=mi;
                }
                else e=mi-1;
            }
            now=pr[j-1][an];
            f[i][j]=now.X*a[i]+now.Y;
            //cout<<pr[j-1].size()<<' '<<i<<' '<<j<<' '<<now.X<<' '<<now.Y<<' '<<a[i]<<' '<<f[i][j]<<'\n';
            now=line(a[i],f[i][j]-a[i]*a[i]);


            ps x;
            while(pr[j].size()>1){
                x=giao(pr[j].back(),now);
                if((x.Y==0 && now.Y>=pr[j].back().Y) || cmp(x,ad[j].back())){
                    pr[j].pop_back();ad[j].pop_back();
                }
                else break;
            }
            x=giao(pr[j].back(),now);
            pr[j].pb(now);
            ad[j].pb(x);
        }
        now=line(a[i],-a[i]*a[i]);
        ps x;
        while(pr[1].size()>1){
            x=giao(pr[1].back(),now);
            if((x.Y==0 && now.Y>=pr[1].back().Y) || cmp(x,ad[1].back())){
                pr[1].pop_back();ad[1].pop_back();
            }
            else break;
        }
        x=giao(pr[1].back(),now);
        pr[1].pb(now);
        ad[1].pb(x);
    }
    cout<<f[n][m] << "\n";
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:52:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |                 int mi=b+e>>1;
      |                        ~^~
sequence.cpp:102:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |                 int mi=b+e>>1;
      |                        ~^~
sequence.cpp:110:27: warning: 'an' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |             now=pr[j-1][an];
      |                           ^
sequence.cpp:59:27: warning: 'an' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |             now=pr[j-1][an];
      |                           ^

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