Submission #469229

#	Time	Username	Problem	Language	Result	Execution time	Memory
469229		amirmohammad_nezami	Split the sequence (APIO14_sequence)	C++14	60 / 100	2078 ms	83400 KiB

sequence

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

#define F first
#define S second
#define PB push_back
#define ll long long
#define _sz(e) e.size()
#define pii pair <int , int>
#define FAST ios::sync_with_stdio(0); cin.tie(0);

#pragma GCC target("sse4,avx,avx2")
#pragma GCC optimize("O3,unroll-loops")

const ll maxn = 1e5 + 4 , N = 200 + 4 , mod = 1e9 + 7 , INF = 1e18;

int n , k , a[maxn] , par[maxn][N];
ll dp[4][maxn] , ps[maxn];

void get(int l , int r , int ql , int qr , int K) {
    if(r - l < 1 || qr - ql < 1) return ;

    int b = (K & 1) , mid = (l + r) / 2 , id = -1;
    dp[b][mid] = INF;
    for (int i = ql; i < min(qr , mid); ++i) {
        ll val = (ps[mid + 1] - ps[i + 1]) * (ps[mid + 1] - ps[i + 1]);
        if(dp[b ^ 1][i] + val < dp[b][mid]) {
            id = i , dp[b][mid] = dp[b ^ 1][i] + val;
        }
    }   
    par[mid][K] = id;
    get(l , mid , ql , id + 1 , K);
    get(mid + 1 , r , id , qr , K);
}

int32_t main() {
    FAST;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ps[i + 1] = ps[i] + a[i];
        dp[1][i] = ps[i + 1] * ps[i + 1]; 
        par[i][1] = -1;
    }

    for (int i = 2; i <= k + 1; ++i) {
        get(0 , n , 0 , n , i);
    }
    int b = ((k + 1) & 1);

    cout << ((ps[n] * ps[n]) - dp[b][n - 1]) / 2 << '\n';

    int c_id = n - 1 , c_k = k + 1;
    while(c_k > 0 && par[c_id][c_k] != -1) {
        cout << par[c_id][c_k] + 1 << ' ';
        c_id = par[c_id][c_k];
        c_k--;
    }
    cout << '\n';
}

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