Submission #551569

#	Time	Username	Problem	Language	Result	Execution time	Memory
551569		hibiki	Split the sequence (APIO14_sequence)	C++11	89 / 100	626 ms	87996 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[2];
int poi[2];

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

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