Submission #1107040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107040		BLOBVISGOD	Split the sequence (APIO14_sequence)	C++17	100 / 100	551 ms	84080 KiB

sequence

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;


const int N = 100003, R = 203;
int dp[R][N]; // store dp[i^1]


struct f{
    ll top, bot;
    bool operator<=(f b){
        return (__int128_t) top*b.bot <= (__int128_t) b.top*bot;
    }bool operator<(f b){
        return (__int128_t) top*b.bot < (__int128_t) b.top*bot;
    }
};

f inter(array<ll,3> a, array<ll,3> b){
    f cur = {a[1]-b[1],b[0]-a[0]};
    if (cur.bot<0) cur = {-cur.top,-cur.bot};
    return cur;
}

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int n,k; cin >> n >> k;
    vector<ll> a(n);
    rep(i,0,n) cin >> a[i];

    /*
        (ai+1 + ai+2 + ... + aj)^2 = sum a_i^2 + all cross terms 
        -> we want to minimize cross terms
        -> for some position, we have dp[i] + (pref[j] - pref[i])^2
        = (dp[i] + pref[i]^2) - 2pref[i]pref[j] + pref[j]^2

        pref[j]^2 is constant, and the rest is a linear function
        with dequeue in O(k*n) -> elements in linear order

        How to retrieve a construction? -> store from in function, only store integers
        100000*200*4 bytes ~ 80mb, fits in memory limit

    */

    vector<ll> pref(n+1);
    rep(i,0,n) pref[i+1] = pref[i] + a[i];
    auto get = [&](int l, int r) -> ll {
        return pref[r] - pref[l];
    };

    ll ans;

    deque<array<ll,3>> curlines, nxtlines; // ax + b, from
    curlines.push_back({0,0,0});
    rep(iter,0,k+1){
        // -2pref decreases, we want min -> push to end, retrieve from front
        swap(nxtlines,curlines);
        curlines.clear();

        rep(i,0,n){
            while(sz(nxtlines)>1 and inter(nxtlines[0],nxtlines[1]) < (f){pref[i+1],1}) nxtlines.pop_front();
            ll cur = nxtlines[0][0]*pref[i+1] + nxtlines[0][1] + pref[i+1]*pref[i+1];
            if (iter == k and i==n-1) cout << (pref[n]*pref[n] - cur)/2 << '\n';


            dp[iter][i+1] = nxtlines[0][2];

            array<ll,3> line = {-2*pref[i+1], cur + pref[i+1]*pref[i+1],i+1};
            while (sz(curlines)>1 and inter(curlines.back(), line) <= inter(curlines[sz(curlines)-2],curlines.back())) curlines.pop_back();
            curlines.push_back(line);
        }
    }

    vi sol;
    int at = n;
    for(int i = k; i>0; i--){
        int nxt = dp[i][at];
        sol.push_back(nxt);
        at = nxt;
    }
    sort(all(sol));
    sol.erase(unique(all(sol)),end(sol));
    vector<bool> vis(n);
    for(auto c : sol) vis[c-1] = 1;
    int cc = 0;
    while(sz(sol)<k){
        if (!vis[cc]) sol.push_back(cc+1);
        cc++;
    }
    sort(all(sol));

    for(auto c : sol) cout << c << ' ';
    cout << '\n';

    
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:54:10: warning: variable 'get' set but not used [-Wunused-but-set-variable]
   54 |     auto get = [&](int l, int r) -> ll {
      |          ^~~
sequence.cpp:58:8: warning: unused variable 'ans' [-Wunused-variable]
   58 |     ll ans;
      |        ^~~

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