Submission #551573

#	Time	Username	Problem	Language	Result	Execution time	Memory
551573		hibiki	Split the sequence (APIO14_sequence)	C++11	100 / 100	738 ms	86596 KiB

sequence

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

#define F first
#define S second

struct LINE
{
    long long m,c;
    int idx;
};

int n,k,back[100010][205];
int qs[100010];
vector<LINE> stk;
queue<LINE> q[2];
int poi;

long long get_y(LINE p,long long x)
{
    return p.m*x+p.c;
}

long long chk(LINE a,LINE b,LINE c) // if positive xa > xb
{
    return (c.c-a.c)*(b.m-c.m) - (c.c-b.c)*(a.m-c.m);
}

void push(LINE p)
{
    while(stk.size()>=2 && chk(stk[stk.size()-2],stk[stk.size()-1],p)>0)
    {
        stk.pop_back();
        //printf("pop hap\n");
    }
    while(stk.size()>=1 && stk[stk.size()-1].m==p.m && stk[stk.size()-1].c<=p.c)
    {
        //printf("pop: %d %d\n",stk[cnt][stk[cnt].size()-1],p.c);
        stk.pop_back();
        //printf("pop hap\n");
    }
    stk.push_back(p);
}

pair<long long,int> query(long long x)
{
    if(poi>=stk.size())
        poi=stk.size()-1;
    //printf("poi%d: %d %d\n",cnt,poi[cnt],stk[cnt][poi[cnt]].idx);
    //printf("%d %d %d\n",poi[cnt],stk[cnt][poi[cnt]].idx,idx);
    while(poi+1<stk.size() && get_y(stk[poi],x)<=get_y(stk[poi+1],x))
        poi++;
    //printf("poi%d: %d %d\n",cnt,poi[cnt],stk[cnt][poi[cnt]].idx);
    return {get_y(stk[poi],x),stk[poi].idx};
}

long long qsl(int l,int r)
{
    return qs[r]-qs[l-1];
}

main()
{
    qs[0]=0;

    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&qs[i]);
        qs[i]=qs[i]+qs[i-1];
    }
    long long ans=0;
    int bb=-1;
    // for(int i=1;i<n;i++)
    // {
    //     //printf("-----%d-----\n",i);
    //     for(int j=min(i,k);j>=2;j--)
    //     {
    //     }
    // }
    LINE temp;
    for(int i=1;i<n;i++)
    {
        long long dp=qsl(1,i)*qsl(i+1,n);
        back[i][1]=0;
        //printf("1 %lld %d\n",dp[i][1],back[i][1]);
        temp.m=(long long)qs[i];
        temp.c=dp-(long long)qs[i]*(long long)qs[n];
        temp.idx=i;
        //printf("push: %lld %lld\n",temp.m,temp.c);
        q[1%2].push(temp);
        if(1==k&&ans<=dp)
        {
            ans=dp;
            bb=i;
        }
    }
    for(int j=2;j<=k;j++)
    {
        poi=0;
        for(int i=j;i<n;i++)
        {
            push(q[(j+1)%2].front());
            q[(j+1)%2].pop();
            pair<long long,int> ret=query(qs[i]);
            long long dp=ret.F+(long long)qs[i]*((long long)qs[n]-(long long)qs[i]);
            back[i][j]=ret.S;
            //printf("%d %lld %d\n",j,dp[i][j],back[i][j]);
            temp.m=qs[i];
            temp.c=dp-(long long)qs[i]*(long long)qs[n];
            temp.idx=i;
            //printf("push: %lld %lld\n",temp.m,temp.c);
            q[j%2].push(temp);
            if(j==k&&ans<=dp)
            {
                ans=dp;
                bb=i;
            }
        }
        q[(j+1)%2].pop();
        stk.clear();
    }
    int nw=k;
    printf("%lld\n",ans);
    while(bb)
    {
        printf("%d ",bb);
        bb=back[bb][k--];
    }
}

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, int> query(long long int)':
sequence.cpp:47:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<LINE>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     if(poi>=stk.size())
      |        ~~~^~~~~~~~~~~~
sequence.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<LINE>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while(poi+1<stk.size() && get_y(stk[poi],x)<=get_y(stk[poi+1],x))
      |           ~~~~~^~~~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main()
      | ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:123:9: warning: unused variable 'nw' [-Wunused-variable]
  123 |     int nw=k;
      |         ^~
sequence.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
sequence.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d",&qs[i]);
      |         ~~~~~^~~~~~~~~~~~~

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