제출 #1227937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227937		395333em	Split the sequence (APIO14_sequence)	C++20	22 / 100	3 ms	1352 KiB

sequence

#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int, int>

using namespace std;

const int mod = 1e9 + 7;
const int inf = 1e18;
int LR = 5e12 + 5;
const int N = 1e5 + 5;
const int K = 2e2 + 5;

int n, k, a[N], pref[N], dp[2][N];
int32_t pos[K][N];

struct line {
    int m, c, idx;
    line(int mm, int cc, int idxx) : m(mm), c(cc), idx(idxx) {}
    int cal(int x){
        return m * x + c;
    }
    long double findx(line cur){
        return (long double)(c - cur.c) / (cur.m - m);
    }
};

struct convexhull {
    deque <line> dq;
    void update(line cur){
        while (dq.size() > 1 && cur.findx(dq[dq.size() - 1]) >= dq[dq.size() - 1].findx(dq[dq.size() - 2])) dq.pop_back();
        dq.emb(cur);
    }
    pii query(int val){
        while (dq.size() > 1 && dq[0].cal(val) <= dq[1].cal(val)) dq.pop_front();
        return {dq.front().cal(val), dq.front().idx};
    }
} hull;

signed main(){
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i], pref[i] = pref[i - 1] + a[i];
    LR = pref[n];
    for (int i = 1; i <= n; i++) dp[0][i] = -inf; 
    dp[0][0] = 0;
    for (int i = 1; i <= k; i++) {
        dp[i % 2][0] = -inf;
        hull.dq.clear();
        hull.update(line(-pref[0], dp[(i - 1) % 2][0], 0));
        for (int j = 1; j <= n; j++) {
            pii curr = hull.query(pref[n] - pref[j]);
            curr.first += pref[j] * pref[n] - pref[j] * pref[j];
            dp[i % 2][j] = curr.first;
            pos[i][j] = curr.second;
            hull.update(line(-pref[j], dp[(i - 1) % 2][j], j));
            // cout << i << ", " << j << " : " << dp[i][j] << ", " << pos[i][j] << "\n";
        }
    }
    int ans = -inf, idx = 0, curk = k;
    for (int i = 1; i <= n; i++) {
        if (dp[k % 2][i] >= ans) ans = dp[k % 2][i], idx = i;
    }
    cout << ans << "\n";
    if (ans == 0) {
        for (int i = 1; i <= k; i++) cout << i << " ";
    }
    else {
        while (curk > 0) {
            cout << idx << " ";
            idx = pos[curk--][idx];
        }
    }
}

/*

*ORDER OF SPLIT DOESN'T MATTER*

dp[i][j] = max score after splitting i'th round at after position j
dp[i][j] = max(dp[i - 1][k] + (pref[j] - pref[k]) * (pref[n] - pref[j]))
dp[i][j] = max(dp[i - 1][k] + pref[j] * pref[n] - pref[j]^2 - pref[k] * pref[n] + pref[k] * pref[j])
dp[i][j] = pref[j] * pref[n] - pref[j]^2 + max(dp[i - 1][k] - pref[k] * (pref[n] - pref[j]))

const = pref[j] * pref[n] - pref[j]^2
m = -pref[k]
x = pref[n] - pref[j]
c = dp[i - 1][k]

*/

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