Submission #331468

#	Time	Username	Problem	Language	Result	Execution time	Memory
331468		ftkbrian	Split the sequence (APIO14_sequence)	C++14	100 / 100	823 ms	84700 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz size()
#define pb pop_back()

ll Dp[101010][2];
int Dir[101010][202],n,k,pos,a,b;
ll S[101010];
struct line{ll a,b,num;};

double cross(line a,line b){return (double)(b.b-a.b)/(a.a-b.a);}
vector<line> cht;
vector<int> ans;

ll Q(ll x,int& d)
{
    while(pos < cht.sz-1 && cross(cht[pos],cht[pos+1]) <= x) pos++;
    d = cht[pos].num;
    return cht[pos].a * x + cht[pos].b;
}
void push(line x)
{
    if(!cht.empty())
    {
        if(cht[cht.sz-1].a == x.a) return;// 얘는 안넣음
    }
    while(cht.sz > 1)
    {
        if(cross(cht[cht.sz-1],cht[cht.sz-2]) <= cross(cht[cht.sz-1],x)) break;
        cht.pb;
    }
    cht.push_back(x);
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);

    cin>>n>>k;
    for(int i = 1 ; i <= n ; i++) cin>>S[i],S[i] += S[i-1];

    for(int i = 1 ; i <= n ; i++) Dp[i][1] = S[i]*S[i];
    for(int i = 2 ; i <= k+1 ; i++)
    {
        cht.clear(),pos = 0,b=(i+1)%2;
        cht.push_back({-2*S[i-1],S[i-1]*S[i-1]+Dp[i-1][b],i-1});
        for(int q = i ; q <= n ; q++)
        {
            Dp[q][i%2] = Q(S[q],Dir[q][i])+S[q]*S[q];
            push({-2*S[q],S[q]*S[q]+Dp[q][b],q});
        }
    }

    cout<<(S[n]*S[n]-Dp[n][(k+1)%2])/2<<"\n";
    ll tar = Dir[n][k+1];
    for(int i = k+1 ; i > 1 ; i--)
    {
        ans.push_back(tar);
        tar = Dir[tar][i-1];
    }
    for(int i = ans.size()-1 ; i > -1 ; i--) cout<<ans[i]<<" ";
}

Compilation message (stderr)

sequence.cpp: In function 'll Q(ll, int&)':
sequence.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     while(pos < cht.sz-1 && cross(cht[pos],cht[pos+1]) <= x) pos++;
      |           ~~~~^~~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:35:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main()
      |      ^

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