Submission #736070

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

sequence

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

struct line {
    long long c;
    int m, id;
    long long value(int x) {
        return (long long) m * x + c;
    }
    line *left, *right;
    line(int a, long long 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<long long, 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, long long c, int id) {
        if (l_ == NULL || l == r) return new line(m, c, id);
        int mid = l + r >> 1;
        if ((long long) m * mid + c > l_->value(mid)) swap(m, l_->m), swap(c, l_->c), swap(id, l_->id);
        if ((long long) 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, long long b, int id) {
        insert(root, 0, 1000000001, a, b, id);
    }
    pair<long long, int> query(int x) {
        return query(root, 0, 1000000001, x);
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    long long ans;
    cin >> n >> k;
    vector<int> a(n + 1), pre(n + 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];
    vector<long long> to;
    for (int i = 1; i <= n; i++) {
        to.push_back(0);
        for (int j = 1; j <= min(k, i - 1); j++) {
            auto [x, y] = lct[j].query(pre[i]);
            if (i == n && j == k) ans = x;
            to.push_back(x);
            par[i][j] = y;
        }
        for (int j = 1; j <= min(i, k); j++) lct[j].insert(pre[i], to[j - 1] - (long long) pre[i] * pre[i], i);
        to.clear();
    }
    cout << ans << '\n';
    for (int x = par[n][k], i = k; i >= 1; i--, x = par[x][i])
        cout << x << ' ';
}

Compilation message (stderr)

sequence.cpp: In constructor 'line::line(int, long long int, int)':
sequence.cpp:6:9: warning: 'line::m' will be initialized after [-Wreorder]
    6 |     int m, id;
      |         ^
sequence.cpp:5:15: warning:   'long long int line::c' [-Wreorder]
    5 |     long long c;
      |               ^
sequence.cpp:11:5: warning:   when initialized here [-Wreorder]
   11 |     line(int a, long long b, int d) : m(a), c(b), id(d), left(NULL), right(NULL) { };
      |     ^~~~
sequence.cpp: In member function 'std::pair<long long int, int> mylichaotree::query(line*, int, int, int)':
sequence.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int mid = l + r >> 1;
      |                   ~~^~~
sequence.cpp: In member function 'line* mylichaotree::insert(line*, int, int, int, long long int, int)':
sequence.cpp:28:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         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