Submission #670218

#	Time	Username	Problem	Language	Result	Execution time	Memory
670218		yyhjin12	Split the sequence (APIO14_sequence)	C++17	100 / 100	474 ms	82784 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef tuple<ll, ll, double, ll> t;

int N, K;
vector<ll> psum;

double intersect(t L1, t L2) {
    return (get<1>(L2)-get<1>(L1))/(get<0>(L1)-get<0>(L2));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> K; psum.resize(N);
    for (auto &i: psum) cin >> i;
    for (int i=1; i<N; i++) psum[i] = psum[i-1] + psum[i];

    int prev[K][N];
    ll DP[2][N];
    t g;
    
    fill(&prev[0][0], &prev[K-1][N], 0);
    fill(&DP[0][0], &DP[1][N], 0);

    for (int k=0; k<K; k++) {
        deque<t> F; F.push_front(t(0, ll(-1e14), -1, -1));
        for (int i=k+1; i<N; i++) {
            g = t(psum[i-1], DP[(k%2)^1][i-1]-(psum[i-1]*psum[i-1]), 0, i-1);
            if (get<0>(F.back()) == get<0>(g) && get<1>(F.back()) < get<1>(g)) {
                F.pop_back();
                while (!F.empty()) {
                    g = t(get<0>(g), get<1>(g), intersect(F.back(), g), get<3>(g));
                    if (get<2>(F.back()) < get<2>(g)) break;
                    F.pop_back();
                }
                F.push_back(g);
            }
            else if (get<0>(F.back()) != get<0>(g)) {
                while (!F.empty()) {    
                    g = t(get<0>(g), get<1>(g), intersect(F.back(), g), get<3>(g));
                    if (get<2>(F.back()) < get<2>(g)) break;
                    F.pop_back();
                }
                F.push_back(g);
            }

            ll X = psum[i];
            while (F.size() > 1 && get<2>(F.at(1)) < X) F.pop_front();
            DP[k%2][i] = get<0>(F.front()) * X + get<1>(F.front());
            prev[k][i] = get<3>(F.front());
        }
    }

    cout << DP[(K-1)%2][N-1] << '\n';

    int temp = N-1, q = K-1;
    vector<int> L;
    while (q>=0) {
        L.push_back(prev[q][temp]+1);
        temp = prev[q--][temp];
    }
    sort(L.begin(), L.end());
    for (auto &i: L) cout << i << ' ';
}

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