Submission #1116342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116342		tjgus1668	Split the sequence (APIO14_sequence)	C++17	60 / 100	2069 ms	82764 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef long double ld;
typedef tuple<ll, ll, int> line; // x, y, idx

vector<line> lines;

ld inter(int a, int b) {
    return (ld)(get<1>(lines[b]) - get<1>(lines[a])) / (ld)(get<0>(lines[a]) - get<0>(lines[b]));
}

void add(line l) {
    lines.push_back(l);
    int n;
    while ((n = lines.size()) >= 3 && inter(n - 1, n - 2) < inter(n - 2, n - 3)) {
        swap(lines[n - 2], lines[n - 1]);
        lines.pop_back();
    }
}

int query(int x) {
    int s = 0, e = lines.size() - 1;
    while (s < e) {
        int m = (s + e) / 2;
        if (inter(m, m + 1) < x) s = m + 1;
        else e = m;
    }
    return e;
}

ll dp[2][100005], a[100005];
int pre[205][100005];
vector<int> ans;


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int N, K; cin >> N >> K;
    for (int i = 1; i <= N; i++) cin >> a[i], a[i] += a[i - 1];

    for (int k = 1; k <= K; ++k) {
        auto &cur = dp[k % 2], &prev = dp[(k + 1) % 2];
        lines.clear();
        add({a[1], prev[0] - a[1] * a[1], 1});

        for (int i = 2; i <= N; ++i) {
            int j = query(a[i]);
            auto [x, y, idx] = lines[j];
            cur[i] = a[i] * a[idx] + prev[idx] - a[idx] * a[idx];
            pre[k][i] = idx;
            if (a[i] - a[i - 1] == 0) continue;
            add({a[i], prev[i] - a[i] * a[i], i});
        }
    }

    int p = N;
    ll res = dp[K % 2][p];
    for (int k = K; k >= 1; --k) {
        auto& cur = dp[k % 2];
        p = pre[k][p];
        ans.push_back(p);
    }
    reverse(ans.begin(), ans.end());

    cout << res << '\n';
    for (auto& x : ans) cout << x << ' ';

    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:62:15: warning: unused variable 'cur' [-Wunused-variable]
   62 |         auto& cur = dp[k % 2];
      |               ^~~

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