Submission #551556

#	Time	Username	Problem	Language	Result	Execution time	Memory
551556		hibiki	Split the sequence (APIO14_sequence)	C++11	71 / 100	198 ms	131072 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];
//long long dp[100010][205];
vector<LINE> stk[205];
int poi[205];

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

pair<long long,int> query(long long x,int cnt)
{
    if(poi[cnt]>=stk[cnt].size())
        poi[cnt]=stk[cnt].size()-1;
    //printf("poi%d: %d %d\n",cnt,poi[cnt],stk[cnt][poi[cnt]].idx);
    while(poi[cnt]+1<stk[cnt].size() && get_y(stk[cnt][poi[cnt]],x)<=get_y(stk[cnt][poi[cnt]+1],x))
        poi[cnt]++;
    //printf("poi%d: %d %d\n",cnt,poi[cnt],stk[cnt][poi[cnt]].idx);
    return {get_y(stk[cnt][poi[cnt]],x),stk[cnt][poi[cnt]].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);
        LINE temp;
        for(int j=min(i,k);j>=2;j--)
        {
            pair<long long,int> ret=query(qs[i],j-1);
            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);
            push(temp,j);
            if(j==k&&ans<=dp)
            {
                ans=dp;
                bb=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);
        push(temp,1);
        if(1==k&&ans<=dp)
        {
            ans=dp;
            bb=i;
        }
    }
    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, int)':
sequence.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<LINE>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     if(poi[cnt]>=stk[cnt].size())
      |        ~~~~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:50:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<LINE>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     while(poi[cnt]+1<stk[cnt].size() && get_y(stk[cnt][poi[cnt]],x)<=get_y(stk[cnt][poi[cnt]+1],x))
      |           ~~~~~~~~~~^~~~~~~~~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:61:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   61 | main()
      | ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:108:9: warning: unused variable 'nw' [-Wunused-variable]
  108 |     int nw=k;
      |         ^~
sequence.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
sequence.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         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: 0 / 29