Submission #1265256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265256		canhnam357	수열 (APIO14_sequence)	C++20	100 / 100	953 ms	87512 KiB

sequence

#include <bits/stdc++.h>
#define int long long
#define sqr(x) ((x) * (x))
#define MASK(i) (1LL << (i))
using namespace std;
const int inf = 1e18;


// y = a * x + b
struct Line {
    int a;
    int b;
};
bool operator < (Line a, Line b) {
    return true;
}
int lower_divide(int a, int b) {
    return a / b;
}
int upper_divide(int a, int b) {
    return (a+b-1) / b;
}
// Duoc dat trong comment la dao chieu hull
struct Hull {
    vector<int> pos;
    vector<int> trace;
    vector<Line> lines;
    Hull(Line first, int id) {
        pos.emplace_back(-inf);
//        pos.emplace_back(inf);
        lines.emplace_back(first);
        trace.emplace_back(id);
    }
    // Them duong thang voi a tang dan
    // Trong comment: them duong thang voi a giam dan
    void update(Line l, int id) {
        int A = l.a;
        int B = l.b;
        if(A == lines.back().a) {
            return;
        }
        while(true) {
            int A1 = lines.back().a;
            int B1 = lines.back().b;
            int X1 = pos.back();
            // A * X + B == A1 * X + B1
            int intersect = lower_divide(B - B1, A1 - A);
//            int intersect = upper_divide(B - B1, A1 - A);
            if(intersect <= X1) {
//            if(intersect >= X1) {
                pos.pop_back();
                lines.pop_back();
                trace.pop_back();
            }
            else {
                pos.push_back(intersect);
                lines.push_back({A, B});
                trace.emplace_back(id);
                break;
            }
        }
    }
    int pre_p = 0;
    int query(int X) {
        int p = lower_bound(pos.begin(), pos.end(), X) - pos.begin() - 1;
//        int p = lower_bound(pos.begin(), pos.end(), X, greater<int>()) - pos.begin() - 1;
        pre_p = p;
        Line l = lines[p];
        return l.a * X + l.b;
    }
    int query_trace(int X) {
        return trace[pre_p];
    }
};
int32_t trace[201][100001];
int32_t main() {
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    srand(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n+1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    vector<int> pre = a;
    for(int i = 1; i <= n; i++)
        pre[i] += pre[i-1];
    vector<int> dp(n+1);
    vector<int> dp_cur(n+1);
    for(int i = 0; i <= n; i++) {
        dp[i] = sqr(pre[i]);
        trace[0][i] = 0;
    }
    for(int j = 1; j <= k; j++) {
        Hull hull({-2 * pre[j], dp[j] + sqr(pre[j])}, j);
        for(int i = j+1; i <= n; i++) {
            int X = pre[i];
            dp_cur[i] = hull.query(X) + sqr(X);
            trace[j][i] = hull.query_trace(X);
            int new_A = -2 * pre[i];
            int new_B = dp[i] + sqr(pre[i]);
            hull.update({new_A, new_B}, i);
        }
        swap(dp, dp_cur);
    }
    int ans = (sqr(pre[n]) - dp[n]) / 2;
    cout << ans << "\n";
    vector<int> block;
    int pos = n;
    for(int j = k; j > 0; j--) {
        block.push_back(trace[j][pos]);
        pos = trace[j][pos];
    }
    reverse(block.begin(), block.end());
    for(int i : block)
        cout << i << " ";
    cout << "\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