Submission #630076

#	Time	Username	Problem	Language	Result	Execution time	Memory
630076		chonka	Split the sequence (APIO14_sequence)	C++17	71 / 100	2067 ms	36784 KiB

sequence

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
#define fi first
#define se second
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 1e5 + 7 ;

struct Line {
    mutable ll k , m , p , id ;
    bool operator < ( const Line& o ) const { return k < o.k ; }
    bool operator < ( ll x ) const { return p < x ; }
};

struct LineContainer : multiset < Line , less < > > {
    static const ll inf = LLONG_MAX ;
    ll div ( ll a , ll b ) {
        return a / b - ( ( a ^ b ) < 0 && a % b ) ;
    }
    bool isect ( iterator x , iterator y ) {
        if ( y == end ( ) ) { return x->p = inf , 0 ; }
        if ( x->k == y->k ) { x->p = x->m > y->m ? inf : -inf ; }
        else { x->p = div ( y->m - x->m , x->k - y->k ) ; }
        return x->p >= y->p ;
    }
    void add ( ll k , ll m , int id ) {
        auto z = insert ( { k , m , 0 , id } ) , y = z ++ , x = y ;
        while ( isect ( y , z ) ) { z = erase ( z ) ; }
        if ( x != begin ( ) && isect ( -- x , y ) ) {
            isect ( x , y = erase ( y ) ) ;
        }
        while ( ( y = x ) != begin ( ) && ( -- x )->p >= y->p ) {
            isect ( x , erase ( y ) ) ;
        }
    }
    pair < ll , int > query ( ll x ) {
        assert ( !empty ( ) ) ;
        auto l = *lower_bound ( x ) ;
        return { l.k * x + l.m , l.id } ;
    }
};

int n , k ;
int a[ MAXN ] ;
ll pref[ MAXN ] ;
ll dp[ 2 ][ MAXN ] ;
int hh[ 202 ][ MAXN ] ;


void solve ( ) {
    cin >> n >> k ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
        pref[ i ] = pref[ i - 1 ] + a[ i ] ;
    }
    int prv = 0 , nxt = 1 ;
    for ( int lvl = 2 ; lvl <= k + 1 ; ++ lvl ) {
        LineContainer w ;
        w.add ( pref[ lvl - 1 ] , dp[ prv ][ lvl - 1 ] - pref[ lvl - 1 ] * pref[ lvl - 1 ] , lvl - 1 ) ;
        for ( int i = lvl ; i <= n ; ++ i ) {
            tie ( dp[ nxt ][ i ] , hh[ lvl ][ i ] ) = w.query ( pref[ i ] ) ;
            w.add ( pref[ i ] , dp[ prv ][ i ] - pref[ i ] * pref[ i ] , i ) ;
        }
        prv ^= 1 , nxt ^= 1 ;
    }
    cout << dp[ prv ][ n ] << "\n" ;
    vector < int > ans ;
    int x = n , y = k + 1 ;
    while ( y > 1 ) {
        ans.push_back ( hh[ y ][ x ] ) ;
        x = hh[ y ][ x ] ; -- y ;
    }
    reverse ( ans.begin ( ) , ans.end ( ) ) ;
    for ( auto x : ans ) {
        cout << x << " " ;
    }
    cout << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

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