Submission #567653

#	Time	Username	Problem	Language	Result	Execution time	Memory
567653		toastifishi	Split the sequence (APIO14_sequence)	C++14	0 / 100	11 ms	2004 KiB

sequence

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;
using ll = long long;

const ll MAXN = 1e5 + 1;
const ll MAXK = 201;

struct line {
    ll x, y, z;
};
struct hull {
    int i;
    vector <line> L, tt;
    void init() {
        i = 0;
        L = tt;
    }
    ll f(ll ii, ll x) { return L[ii].x * x + L[ii].y; }
    void push(line l) {
        int sz = L.size() - 1;
        if(sz && l.x == L[sz].x) {
            L[sz].z = l.z;
            return;
        }
        while(sz > 0 && (L[sz].y - l.y) * (L[sz].x - L[sz - 1].x) < (L[sz - 1].y - L[sz].y) * (l.x - L[sz].x)) {
            sz--;
            L.pop_back();
        }
        L.push_back(l);
    }
    pair <ll, ll> query(ll pos) {
        if(L.size() == 1) return {f(0, pos), L[0].z};
        while(i + 1 < L.size() && f(i + 1, pos) > f(i, pos)) i++;
        return {f(i, pos), L[i].z};
    }
} CHT;


int n, k;
vector <int> res;
int track[MAXK][MAXN];
int arr[MAXN], prefix[MAXN];
ll dp[2][MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        prefix[i] = prefix[i - 1] + arr[i];
    }
    for(int i = 1; i <= k; i++) {
        CHT.init();
        CHT.push({0, 0, 0});
        for(int j = 1; j <= n; j++) {
            auto cur = CHT.query(prefix[j]);
            dp[i & 1][j] = cur.x;
            track[i][j] = cur.y;
            CHT.push({prefix[j], dp[i - 1 & 1][j] - prefix[j] * prefix[j], j});
        }
    }
    cout << dp[k & 1][n] << "\n";
    int cur = n;
    res.push_back(-1);
    for(int i = k; i >= 1; i--) {
        res.push_back(track[i][cur]);
        cur = track[i][cur];
    }
    sort(res.begin(), res.end());
    for(int i = 1; i <= k; i++) {
        if(!res[i]) res[i] = 1; 
        if(res[i] <= res[i - 1]) res[i] = res[i - 1] + 1;
    }
    for(int i = 1; i <= k; i++) cout << res[i] << " ";
    return 0;
}

Compilation message (stderr)

sequence.cpp: In member function 'std::pair<long long int, long long int> hull::query(ll)':
sequence.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while(i + 1 < L.size() && f(i + 1, pos) > f(i, pos)) i++;
      |               ~~~~~~^~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:64:39: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   64 |             CHT.push({prefix[j], dp[i - 1 & 1][j] - prefix[j] * prefix[j], j});
      |                                     ~~^~~

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