제출 #1186365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186365		dombly	Split the sequence (APIO14_sequence)	C++20	100 / 100	803 ms	83064 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

struct line{
    ll m, c, id;
    ll eval(ll x){return m * x + c;}
    ld inter(line l){return (long double)(c - l.c) / (l.m - m);}
};
int n, k;
ll a[100005], dp[100005][2], pre[100005];
int race[100005][202];
deque<ll> dq;

bool bad(__int128_t m1, __int128_t b1, __int128_t m2, __int128_t b2, __int128_t m3, __int128_t b3){
    return (b2 - b1) * (m1 - m3) >= (m1 - m2) * (b3 - b1);
}

int main(){
//    freopen("task.inp","r",stdin);
//    freopen("task.out","w",stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n ; ++i){
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    for(int i = 1 ; i <= n ; ++i)
        dp[i][0] = pre[i] * (pre[n] - pre[i]);
    for(int i = 1; i <= k ; ++i){
        dq.clear();
        for(int j = i + 1 ; j <= n ; ++j){
            ll suf = pre[n] - pre[j];
            while((int)dq.size() >= 2){
                ll s1 = dq.back(), s2 = dq[dq.size() - 2];
                if(bad(-pre[s1],dp[s1][0],-pre[s2],dp[s2][0],-pre[j - 1],dp[j - 1][0]))
                    dq.pop_back();
                else break;
            }
            dq.push_back(j - 1);
            while((int)dq.size() >= 2){
                ll s1 = dq[0];
                ll s2 = dq[1];
                s1 = dp[s1][0] + (pre[j] - pre[s1]) * suf;
                s2 = dp[s2][0] + (pre[j] - pre[s2]) * suf;
                if(s1 <= s2) dq.pop_front();
                else break;
            }
            ll val = dp[dq[0]][0] + (pre[j] - pre[dq[0]]) * suf;
            dp[j][1] = val;
            race[j][i] = dq[0];


        }
        for(int j = i + 1 ; j <= n ; ++j)
            dp[j][0] = dp[j][1];
    }
    ll res = dp[n][1];
    vector<int> v;
    int pos = n;
    for(int i = k ; i >= 1;  --i){
        pos = race[pos][i];
        v.push_back(pos);
    }
    reverse(v.begin(),v.end());
    cout << res << '\n';
    for(int i : v) cout << i << ' ';
    return 0;
}

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