Submission #470682

#	Time	Username	Problem	Language	Result	Execution time	Memory
470682		ymm	Split the sequence (APIO14_sequence)	C++17	100 / 100	625 ms	87184 KiB

sequence

///
///   ♪ Pizza mozzarella rella rella rella... ♪
///

#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef          long long   ll;
typedef unsigned long long  ull;
typedef std::pair<int,int>  pii;
typedef std::pair<ll ,ll >  pll;
using namespace std;

const int N = 100'010;
const int K = 210;
ll dp0[N], dp1[N];
int sp[N][K];
ll a[N];
int n, k;

inline ll ival(pll p, ll x){return p.F*x + p.S;}

int main()
{
    FAST;
    cin >> n >> k;
    Loop(i,0,n) cin >> a[i];
    Loop(i,1,N) dp0[i] = -1e18;
    vector<pair<pll, int>> v(N);
    Loop(j,1,k+2)
    {
        v.clear();
        dp1[0] = 0;
        v.emplace_back(pll{0, 0}, 0);
        int pv = 0;
        ll x = 0;
        Loop(i,0,n)
        {
            x += a[i];
            while(pv+1 < v.size() && ival(v[pv].F, x) <= ival(v[pv+1].F, x)) ++pv;
            dp1[i+1] = ival(v[pv].F, x);
            sp[i+1][j] = v[pv].S;
            pll p = {x, dp0[i+1]-x*x};
            while(v.size() > 1)
            {
                pll q1 = v[v.size()-1].F;
                pll q2 = v[v.size()-2].F;
                if(q1 == p || __int128(q1.S-p.S)*(p.F-q2.F) < __int128(q2.S-p.S)*(p.F-q1.F)) v.pop_back();
                else break;
            }
            v.emplace_back(p,i+1);
            pv = min(pv, (int)v.size()-1);
        }
        Loop(i,0,N) dp0[i] = dp1[i];
    }
    cout << dp0[n] << '\n';
    for(int j = k+1; j >= 2; --j)
    {
        cout << sp[n][j] << ' ';
        n = sp[n][j];
    }
    cout << '\n';
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:47:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             while(pv+1 < v.size() && ival(v[pv].F, x) <= ival(v[pv+1].F, x)) ++pv;
      |                   ~~~~~^~~~~~~~~~

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