Submission #446097

#	Time	Username	Problem	Language	Result	Execution time	Memory
446097		aryan12	Split the sequence (APIO14_sequence)	C++17	100 / 100	1420 ms	81836 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 5, K = 205;
long long dp[2][N], a[N];
int comeFrom[K][N];
int n, k;

void dnc(int l, int r, int col, int bestL, int bestR) {
    if(l > r) {
        return;
    }
    int mid = (l + r) >> 1;
    int pos = col & 1;
    pair<long long, long long> ans = {-1, -1};
    for(int i = bestL; i < min(mid, bestR + 1); i++) {
        long long val = dp[1 - pos][i] + (a[n] - a[mid]) * (a[mid] - a[i]);
        if(val > ans.first) {
            ans = {val, i};
        }
    }
    dp[pos][mid] = ans.first;
    //cout << "col = " << col << ", mid = " << mid << ", ans.first = " << ans.first << "\n";
    comeFrom[col][mid] = ans.second;
    dnc(l, mid - 1, col, bestL, ans.second);
    dnc(mid + 1, r, col, ans.second, bestR);
}

void Solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    for(int j = 0; j <= n; j++) {
        for(int i = 0; i <= k; i++) {
            comeFrom[i][j] = -1;
        }
        dp[0][j] = -1;
        dp[1][j] = -1;
    }
    dp[0][0] = 0;
    for(int i = 1; i <= k; i++) {
        dnc(i, n, i, i - 1, n - 1);
    }
    pair<long long, int> ans = {-1, -1};
    for(int i = 1; i <= n; i++) {
        if(ans.first < dp[k & 1][i]) {
            ans = {dp[k & 1][i], i};
        }
    }
    cout << ans.first << "\n";
    while(k != 0 && ans.second != -1) {
        cout << ans.second << " ";
        ans.second = comeFrom[k--][ans.second];
    }
    cout << "\n";
}

int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\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: 29 / 29