Submission #522837

#	Time	Username	Problem	Language	Result	Execution time	Memory
522837		pokmui9909	Split the sequence (APIO14_sequence)	C++17	100 / 100	751 ms	82316 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lf = long double;
 
#define x first
#define y second
struct Line{
    ll a, b, i;
    ll f(ll x){
        return a * x + b;
    }
};
lf X_cross(Line f, Line g){
    return 1.0 * (f.b - g.b) / (g.a - f.a);
}
 
ll N, K;
ll A[100005];
ll S[100005];
ll D[2][100005];
int T[202][100002];
 
int main(){
    cin.tie(0) -> sync_with_stdio(false);
    
    cin >> N >> K;
    for(int i = 1; i <= N; i++){
        cin >> A[i];
        S[i] = S[i - 1] + A[i];
    }
    for(int i = 1; i <= K; i++){
        ll p = i % 2, q = (i - 1) % 2;
        deque<Line> dq;
        dq.push_back({S[i], D[q][i] - S[i] * S[i], i});
        for(int j = i + 1; j <= N; j++){
            while(dq.size() >= 2 && dq[0].f(S[j]) <= dq[1].f(S[j])) dq.pop_front();
            D[p][j] = dq[0].f(S[j]);
            T[i][j] = dq[0].i;
            Line f = {S[j], D[q][j] - S[j] * S[j], j};
            while(dq.size() >= 2 && X_cross(dq[dq.size() - 1], dq[dq.size() - 2]) >= X_cross(dq[dq.size() - 2], f)) dq.pop_back();
            dq.push_back(f);    
        }
    }
    cout << D[K % 2][N] << '\n';
    ll idx = N;
    for(int i = K; i >= 1; i--){
        idx = T[i][idx];
        cout << idx << ' ';
    }
}

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