Submission #249062

#	Time	Username	Problem	Language	Result	Execution time	Memory
249062		receed	Split the sequence (APIO14_sequence)	C++14	100 / 100	811 ms	86428 KiB

sequence

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 100001, K = 202;
int pr[K][N];
ll cd[N], ps[N], nd[N];

ll f(pair<ll, ll> q, ll x) {
    return q.first * x + q.second;
}

bool td(pair<ll, ll> p1, pair<ll, ll> p2, pair<ll, ll> p3) {
    return (p2.second - p1.second) * (p1.first - p3.first) >= (p3.second - p1.second) * (p1.first - p2.first) &&
           (p3.second - p1.second) * (p2.first - p3.first) >= (p3.second - p2.second) * (p1.first - p3.first);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, k, x;
    cin >> n >> k;
    ll ans = 0;
    vector<ll> a;
    rep(i, n) {
        cin >> x;
        // if (x)
        a.push_back(x);
    }
    n = a.size();
    k = min(k, n - 1);
    rep(i, n) {
        ps[i + 1] = ps[i] + a[i];
        cd[i + 1] = 1e18;
    }
    rep(i, k + 1) {
        vector<pair<ll, ll>> dp;
        vector<int> num;
        ll pos = 0;
        rep(j, n) {
            pair<ll, ll> np = {-2 * ps[j], cd[j] + ps[j] * ps[j]};
            while (dp.size() > 1 && td(dp[dp.size() - 2], dp.back(), np)) {
                dp.pop_back();
                num.pop_back();
            }
            pos = min(pos, (ll) dp.size() - 1);
            dp.push_back(np);
            num.push_back(j);
            while (pos + 1 < dp.size() && f(dp[pos + 1], ps[j + 1]) <= f(dp[pos], ps[j + 1]))
                pos++;
            nd[j + 1] = ps[j + 1] * ps[j + 1] + f(dp[pos], ps[j + 1]);
            pr[i][j + 1] = num[pos];
        }
        rep(j, n + 1)
            cd[j] = nd[j];
    }
    cout << (ps[n] * ps[n] - cd[n]) / 2 << '\n';
    int cp = n;
    for (int i = k; i > 0; i--) {
        cp = pr[i][cp];
        cout << cp << ' ';
    }
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:71:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (pos + 1 < dp.size() && f(dp[pos + 1], ps[j + 1]) <= f(dp[pos], ps[j + 1]))
                    ~~~~~~~~^~~~~~~~~~~
sequence.cpp:45:8: warning: unused variable 'ans' [-Wunused-variable]
     ll ans = 0;
        ^~~

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