Submission #126940

#	Time	Username	Problem	Language	Result	Execution time	Memory
126940		AQT	Split the sequence (APIO14_sequence)	C++14	100 / 100	1787 ms	83548 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

int N, K;
long long pre[100005];
long long dp[100005][2];
int par[100005][205];

inline void solve(int l, int r, int lb, int ub, int lvl){
    if(l > r){
        return;
    }
    int mid = l+r>>1;
    for(int i = lb; i<=min(mid-1, ub); i++){
        if(dp[mid][lvl&1] <= dp[i][lvl&1^1] + pre[i]*(pre[mid] - pre[i])){
            dp[mid][lvl&1] = dp[i][lvl&1^1] + pre[i]*(pre[mid] - pre[i]);
            par[mid][lvl] = i;
        }
    }
    solve(l, mid-1, lb, par[mid][lvl], lvl);
    solve(mid+1, r, par[mid][lvl], ub, lvl);
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> K;
    for(int i = 1; i<=N; i++){
        cin >> pre[i];
        pre[i] += pre[i-1];
    }
    for(int k = 1; k<=K; k++){
        solve(k+1, N, k, N, k);
    }
    cout << dp[N][K&1] << "\n";
    int crnt = N;
    for(int k = K; k>=1; k--){
        cout << par[crnt][k] << " ";
        crnt = par[crnt][k];
    }
    cout << "\n";
}

Compilation message (stderr)

sequence.cpp: In function 'void solve(int, int, int, int, int)':
sequence.cpp:14:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l+r>>1;
               ~^~
sequence.cpp:16:39: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
         if(dp[mid][lvl&1] <= dp[i][lvl&1^1] + pre[i]*(pre[mid] - pre[i])){
                                    ~~~^~
sequence.cpp:17:39: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
             dp[mid][lvl&1] = dp[i][lvl&1^1] + pre[i]*(pre[mid] - pre[i]);
                                    ~~~^~

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