Submission #562836

#	Time	Username	Problem	Language	Result	Execution time	Memory
562836		Ooops_sorry	Split the sequence (APIO14_sequence)	C++14	100 / 100	890 ms	88992 KiB

sequence

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld long double
#define ll long long

mt19937 rnd(51);

const ll INF = 1e18, K = 210;

struct line {
    ll k, b;
    int i;
};

vector<line> q, qq;
int now = -1;

ld intersection(line a, line b) {
    return (ld)(b.b - a.b) / (a.k - b.k);
}

void add(line a) {
    while (q.size() > 1) {
        int sz = q.size();
        if (q.back().k == a.k) {
            if (a.b > q.back().b) {
                q.pop_back();
            } else {
                return;
            }
        }
        if (intersection(q[sz - 2], a) < intersection(q[sz - 2], q[sz - 1])) {
            q.pop_back();
        } else {
            break;
        }
    }
    if (q.size() == 1 && q.back().k == a.k) {
        if (a.b > q.back().b) {
            q.pop_back();
        } else {
            return;
        }
    }
    q.pb(a);
}

pair<ll, int> get(int i, ll x) {
    if (q.size() == 0) return {-INF, -1};
    now = min(now, (int)(q.size()) - 1);
    while (now + 1 < q.size() && intersection(q[now], q[now + 1]) <= x) {
        now++;
    }
    return {x * q[now].k + q[now].b, q[now].i};
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LCOAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<ll> a(n), pr(n), dp(n);
    vector<vector<int>> par(n + 1, vector<int>(k + 1));
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    reverse(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        pr[i] = a[i];
        if (i > 0) {
            pr[i] += pr[i - 1];
        }
        dp[i] = 0;
    }
    ll ans = -1;
    for (int f = 1; f <= k; ++f) {
        vector<ll> dpp(n);
        q.clear();
        now = 0;
        for (int i = 0; i < n; ++i) {
            pair<ll, int> p = get(f - 1, pr[i]);
            dpp[i] = p.first;
            par[i][f] = p.second;
            add({pr[i], dp[i] - pr[i] * pr[i], i});
        }
        swap(dp, dpp);
    }
    cout << dp[n - 1] << endl;
    vector<int> res;
    int i = n - 1, j = k, sum = 0;
    while (j > 0) {
        res.pb(i - par[i][j]);
        i = par[i][j];
        j--;
        sum += res.back();
    }
    int now = 0;
    for (auto to : res) {
        cout << (now += to) << ' ';
    }
    cout << endl;
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, int> get(int, long long int)':
sequence.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     while (now + 1 < q.size() && intersection(q[now], q[now + 1]) <= x) {
      |            ~~~~~~~~^~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:81:8: warning: unused variable 'ans' [-Wunused-variable]
   81 |     ll ans = -1;
      |        ^~~

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