Submission #334972

#	Time	Username	Problem	Language	Result	Execution time	Memory
334972		shahriarkhan	Split the sequence (APIO14_sequence)	C++14	100 / 100	600 ms	85484 KiB

sequence

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

//code copied from arman_ferdous

//dp[i][j] means the maximum cost we can get
//if we do the j'th cut in between a[i] and a[i+1]
//the array m is going to be in increasing order

using ll = long long ;

const int N = 100005 , K = 205 ;

const ll INF = 1e18 ;

int n , k , opt[N][K] ;

ll sum[N] , dp[N][2] ;

struct CHT{
    ll m[N] , b[N] ;
    int idx[N] , siz , last ;
    void init() {siz = last = 0; }
    bool bad(int i , int j , int k)
    {
        return (b[j] - b[i])*(m[i] - m[k]) >= (b[k] - b[i])*(m[i] - m[j]) ;
    }
    void add(ll M , ll B , int idx_)
    {
        m[siz] = M , b[siz] = B , idx[siz] = idx_ , ++siz ;
        while((siz>=3) && bad(siz-3,siz-2,siz-1))
        {
            m[siz-2] = m[siz-1] ;
            b[siz-2] = b[siz-1] ;
            idx[siz-2] = idx[siz-1] ;
            --siz ;
        }
    }
    ll f(int i , ll X) { return (m[i] * X) + b[i] ; }
    pair<ll , int> query(ll X)
    {
        last = min(last , siz-1) ;
        while(((last+1)<siz) && (f(last,X)<=f(last+1,X))) ++last ;
        return {f(last,X),idx[last]} ;
    }
} ds ;

int main()
{
    scanf("%d%d",&n,&k) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        scanf("%lld",&sum[i]) ;
        sum[i] += sum[i-1] ;
    }
    for(int j = 1 ; j <= k ; ++j)
    {
        int col = (j&1) ;
        ds.init() ;
        ds.add(0,0,0) ;
        for(int i = j ; i <= n ; ++i)
        {
            auto got = ds.query(sum[i]) ;
            dp[i][col] = got.first ;
            opt[i][j] = got.second ;
            ds.add(sum[i],dp[i][(col^1)] - (sum[i]*sum[i]),i) ;
        }
    }
    printf("%lld\n",dp[n][(k&1)]) ;
    while(n && k)
    {
        printf("%d ",opt[n][k]) ;
        n = opt[n][k] ;
        --k ;
    }
    return 0 ;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d%d",&n,&k) ;
      |     ~~~~~^~~~~~~~~~~~~~
sequence.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         scanf("%lld",&sum[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