Submission #469232

#	Time	Username	Problem	Language	Result	Execution time	Memory
469232		amirmohammad_nezami	Split the sequence (APIO14_sequence)	C++14	71 / 100	2098 ms	84844 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); cout.tie(0);

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

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

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

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

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

int 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: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29