Submission #736051

#	Time	Username	Problem	Language	Result	Execution time	Memory
736051		Desh03	수열 (APIO14_sequence)	C++17	71 / 100	599 ms	131072 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct line {
    int m, c, id;
    int value(int x) {
        return m * x + c;
    }
    line *left, *right;
    line(int a, int b, int d) : m(a), c(b), id(d), left(NULL), right(NULL) { };
};

struct mylichaotree {
    line *root;
    mylichaotree() {
        root = new line(0, -1000000000, 0);
    }
    pair<int, int> query(line *l_, int l, int r, int x) {
        if (l_ == NULL) return {-1000000000, -1000000000};
        if (l == r) return make_pair(l_->value(x), l_->id);
        int mid = l + r >> 1;
        if (x <= mid) return max(make_pair(l_->value(x), l_->id), query(l_->left, l, mid, x));
        return max(make_pair(l_->value(x), l_->id), query(l_->right, mid + 1, r, x));
    }
    line* insert(line *l_, int l, int r, int m, int c, int id) {
        if (l_ == NULL || l == r) return new line(m, c, id);
        int mid = l + r >> 1;
        if ((m * mid + c) > l_->value(mid)) swap(m, l_->m), swap(c, l_->c), swap(id, l_->id);
        if (m * l + c > l_->value(l)) l_->left = insert(l_->left, l, mid, m, c, id);
        else l_->right = insert(l_->right, mid + 1, r, m, c, id);
        return l_;
    }
    void insert(int a, int b, int id) {
        insert(root, 0, 1000000001, a, b, id);
    }
    pair<int, int> query(int x) {
        return query(root, 0, 1000000001, x);
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1), pre(n + 1);
    vector<vector<int>> dp(n + 1, vector<int> (k + 1));
    vector<vector<int>> par(n + 1, vector<int> (k + 1));
    vector<mylichaotree> lct(k + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] + a[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(k, i - 1); j++) {
            auto [x, y] = lct[j].query(pre[i]);
            dp[i][j] = x, par[i][j] = y;
        }
        for (int j = 1; j <= min(k, i); j++)
            lct[j].insert(pre[i], dp[i][j - 1] - pre[i] * pre[i], i);
    }
    cout << dp[n][k]<< '\n';
    for (int x = par[n][k], i = k; i >= 1; i--, x = par[x][i])
        cout << x << ' ';
}

Compilation message (stderr)

sequence.cpp: In member function 'std::pair<long long int, long long int> mylichaotree::query(line*, long long int, long long int, long long int)':
sequence.cpp:23:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         int mid = l + r >> 1;
      |                   ~~^~~
sequence.cpp: In member function 'line* mylichaotree::insert(line*, long long int, long long int, long long int, long long int, long long int)':
sequence.cpp:29:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         int mid = l + r >> 1;
      |                   ~~^~~

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