Submission #258098

#	Time	Username	Problem	Language	Result	Execution time	Memory
258098		aggu_01000101	Split the sequence (APIO14_sequence)	C++14	71 / 100	626 ms	131076 KiB

sequence

#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <bits/stdc++.h>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define int long long
#define INF 10000000000000000
using namespace std;
#define mid(l, u) ((l+u)/2)
//#define cin fin
//#define cout fout
const int N = 100005;
const int K = 205;
int pref[N];
int n, k;
int dp[K][N];
int nxt[K][N];
stack<pair<pair<int, int>, pair<int, int>>> toEval;
void f(int currk, int l, int r, int ll, int rr){ //dp(currk, m) = best cost when you want to make currk splits with first split starting at m
    if(l>r){
        return;
    }
    int m = mid(l, r);
    //we want to calculate dp[currk][m]
    //look at dp[currk-1][max(ll, m+1)] to dp[currk - 1][min(rr, n - currk)].
    //The answer for dp[curr-1][x] will be (sum(m to x-1) * sum(x to n)) + dp[curr-1][x]
    //base case - dp[0][anything] = 0;
    //cout<<currk<<" "<<m<<" "<<ll<<" "<<rr<<endl;
    //n - x + 1 >= currk
    for(int x = max(ll, m+1);x<=min(rr, n - (currk - 1));x++){
        int tempans = ((pref[x-1] - pref[m-1]) * (pref[n] - pref[x-1])) + dp[currk - 1][x];
        //cout<<"ANS AT "<<x<<" is "<<tempans<<endl;
        if(tempans >= dp[currk][m]){
            nxt[currk][m] = x;
            dp[currk][m] = tempans;
        }
    }
    //cout<<"dp["<<currk<<"]["<<m<<"] = "<<dp[currk][m]<<endl;
    toEval.push({{l, m-1}, {ll, nxt[currk][m]}});
    toEval.push({{m+1, r}, {nxt[currk][m], rr}});
}
signed main(){
    //ofstream fin("2.in");
    //ofstream fout("2.out");
    cin>>n>>k;
    for(int i = 1;i<=n;i++){
        cin>>pref[i];
        pref[i] += pref[i-1];
    }
    for(int currk = 1;currk<=k;currk++){
        f(currk, 1, n - currk, 1, n);
        while(toEval.size()){
            pair<pair<int, int>, pair<int, int>> curr = toEval.top();
            toEval.pop();
            f(currk, curr.first.first, curr.first.second, curr.second.first, curr.second.second);
        }
    }
    cout<<dp[k][1]<<endl;
    int lol = k;
    int currst = 1;
    while(lol){
        cout<<(nxt[lol][currst] - 1)<<" ";
        currst = nxt[lol][currst];
        lol--;
    }
    cout<<endl;
}
/*
7 3
4 1 3 4 0 2 3
 */

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