Submission #84694

#	Time	Username	Problem	Language	Result	Execution time	Memory
84694		popovicirobert	Split the sequence (APIO14_sequence)	C++14	100 / 100	493 ms	85032 KiB

sequence

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long

using namespace std;

const ll INF = 1e18;
const int MAXN = (int) 1e5;
const int MAXK = 200;

ll dp[2][MAXN + 1];
int from[MAXK + 2][MAXN + 1];
ll arr[MAXN + 1];

struct Line {
    ll a, b;
    int pos;
}deq[MAXN + 1];

inline double inter(Line l1, Line l2) {
    if(l1.a == l2.a) {
        return INF;
    }
    return 1.0 * (l2.b - l1.b) / (l1.a - l2.a);
}

inline ll get(Line l, ll x) {
    return 1LL * l.a * x + l.b;
}

int main() {
    //ifstream cin("C.in");
    //ofstream cout("C.out");
    int i, j, n, k;
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for(i = 1; i <= n; i++) {
        cin >> arr[i];
        arr[i] += arr[i - 1];
    }
    for(j = 2; j <= k + 1; j++) {
        memset(dp[j & 1], 0, sizeof(dp[j & 1]));
        int b = 0, e = 0;
        for(i = 1; i <= n; i++) {
            Line l = {arr[i - 1], dp[1 - j & 1][i - 1] - 1LL * arr[i - 1] * arr[i - 1], i - 1};
            while(e > b && inter(deq[e - 1], l) - inter(deq[e], deq[e - 1]) < 0) {
                e--;
            }
            deq[++e] = l;
            while(b < e && get(deq[b], arr[i]) <= get(deq[b + 1], arr[i])) {
                b++;
            }
            dp[j & 1][i] = get(deq[b], arr[i]);
            from[j][i] = deq[b].pos;
        }
    }
    cout << dp[1 - k & 1][n] << "\n";
    vector <int> split;
    int l = k + 1, c = n;
    while(l > 0) {
        c = from[l][c];
        if(c > 0) {
            split.push_back(c);
        }
        l--;
    }
    reverse(split.begin(), split.end());
    for(auto it : split) {
        cout << it << " ";
    }
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:45:40: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
             Line l = {arr[i - 1], dp[1 - j & 1][i - 1] - 1LL * arr[i - 1] * arr[i - 1], i - 1};
                                      ~~^~~
sequence.cpp:57:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
     cout << dp[1 - k & 1][n] << "\n";
                ~~^~~

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