제출 #1288543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288543		harryleee	수열 (APIO14_sequence)	C++20	71 / 100	350 ms	196608 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG_INF = (ll)-9e18;
const ll INF = (ll)9e18;
const int MAXK = 205;
const int MAXN = 100000;

int n, k;
ll a[MAXN + 5];
ll pre[MAXN + 5];
int trace_pos[MAXN + 5][MAXK]; // trace_pos[i][c] = best t for dp[i][c]
ll dp[MAXN + 5][MAXK]; // dp[i][c] = min sumsq for prefix i into c parts

struct line {
    long long a, b;
    mutable long double p;
    int id;
    bool operator < (const line& other) const {
        if (other.a == (long long)1e18 && other.b == (long long)1e18)
            return p < other.p;
        return a < other.a || (a == other.a && b < other.b);
    }
};

struct LINE_CONTAINER {
    multiset<line> ms;
    inline bool del(multiset<line>::iterator x, multiset<line>::iterator y){
        if (y == ms.end()){
            x->p = 1e18;
            return false;
        }
        if (x->a == y->a){
            x->p = (x->b >= y->b) ? 1e18 : -1e18;
        } else {
            x->p = (long double)(y->b - x->b) / (long double)(x->a - y->a);
        }
        return x->p >= y->p;
    }
    inline void update(long long a, long long b, int i){
        auto x = ms.insert({a, b, 0.0L, i});
        auto y = next(x);
        while (del(x, y)) y = ms.erase(y);
        if (x != ms.begin()){
            y = prev(x);
            if (del(y, x)) ms.erase(x);
        } else y = x;
        while (y != ms.begin()){
            x = prev(y);
            if (del(x, y)){
                del(x, ms.erase(y));
                y = x;
            } else break;
        }
    }
    inline pair<long long,int> get(long long x){
        auto it = ms.lower_bound({(long long)1e18, (long long)1e18, (long double)x, 0});
        if (it == ms.end()) return {NEG_INF, 0};
        return { it->a * x + it->b, it->id };
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    if (!(cin >> n >> k)) return 0;
    for (int i = 1; i <= n; ++i) { cin >> a[i]; pre[i] = pre[i-1] + a[i]; }
    // dp[0][0]=0, rest = INF
    for (int i = 0; i <= n; ++i)
        for (int c = 0; c <= k+1; ++c) {
            dp[i][c] = INF;
            trace_pos[i][c] = 0;
        }
    dp[0][0] = 0;

    // c = number of parts (1 .. k+1)
    for (int c = 1; c <= k+1; ++c){
        LINE_CONTAINER lc;
        // We want min_t (dp[t][c-1] + pre[t]^2 - 2*pre[i]*pre[t]).
        // To reuse max-CHT, store lines with a' = 2*pre[t], b' = -(dp[t][c-1] + pre[t]^2),
        // then max(a'*x + b') = - min(dp[t][c-1] + pre[t]^2 - 2*pre[t]*x).
        // So dp[i][c] = pre[i]^2 - max(...)  and trace = id of that line.
        // Insert line for t=0 first (if valid)
        if (dp[0][c-1] < INF/4) lc.update(2LL*pre[0], -(dp[0][c-1] + pre[0]*pre[0]), 0);

        for (int i = 1; i <= n; ++i){
            auto g = lc.get(pre[i]);
            if (g.first != NEG_INF){
                ll val = pre[i]*pre[i] - g.first; // dp[i][c]
                if (val < dp[i][c]){
                    dp[i][c] = val;
                    trace_pos[i][c] = g.second;
                }
            }
            // add line for t = i to be used for later i' > i
            if (dp[i][c-1] < INF/4){
                ll slope = 2LL * pre[i];
                ll intercept = -(dp[i][c-1] + pre[i]*pre[i]);
                lc.update(slope, intercept, i);
            }
        }
    }

    ll total = pre[n]*pre[n];
    ll min_sumsq = dp[n][k+1];
    ll best_points = (total - min_sumsq) / 2; // (S^2 - sum sq)/2
    cout << best_points << '\n';

    // reconstruct cuts: backtrack from (n, k+1)
    vector<int> cuts;
    int cur = n, c = k+1;
    while (c > 0 && cur > 0){
        int prev = trace_pos[cur][c];
        if (prev == 0) break;
        cuts.push_back(prev);
        cur = prev;
        --c;
    }
    reverse(cuts.begin(), cuts.end());
    // We need exactly k cut positions between 1 and n-1: cuts should contain k positions.
    // If cuts contains fewer (some prev were 0), fill none — but normally problem constraints guarantee a solution.
    for (size_t i = 0; i < cuts.size() && (int)i < k; ++i){
        if (i) cout << ' ';
        cout << cuts[i];
    }
    cout << '\n';
    return 0;
}

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