Submission #48688

#	Time	Username	Problem	Language	Result	Execution time	Memory
48688		faishol27	Split the sequence (APIO14_sequence)	C++14	71 / 100	768 ms	25032 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
 
#define fi first
#define se second
 
const int MAXN = 1e4+5;
const int MAXK = 205;

int N, K;
ll data[MAXN], pref[MAXN], suff[MAXN];
ll dp[MAXK][MAXN], ans=0;
int tambah[MAXK][MAXN];
stack<int>putus;

void init(){
    memset(data, 0, MAXN);
    memset(pref, 0, MAXN);
    memset(suff, 0, MAXN);
    memset(dp, -1, sizeof dp);
    memset(tambah, -1, sizeof tambah);

    for(int i=0;i<MAXN;i++) dp[0][i] = 0, tambah[0][i] = 0;
    for(int i=0;i<MAXK;i++) dp[i][0] = 0, tambah[i][0] = 0;
}

void bruteforce(int posK, int ind){
    //cout << posK << " " << ind << ": ";
    for(int l=posK-1;l<ind;l++){
        ll tmp = dp[posK-1][l]+(pref[ind]-pref[l])*suff[ind+1];
        //cout << tmp << " ";
        if(dp[posK][ind] <= tmp){
            dp[posK][ind] = tmp;
            tambah[posK][ind] = l;
        }
    }
    //cout << endl;
}

void bruteforce_search(int posK, int ind, int l, int r){
    //cout << posK << " " << ind << ": ";
    for(;l<=r;l++){
        ll tmp = dp[posK-1][l]+(pref[ind]-pref[l])*suff[ind+1];
        //cout << tmp << " ";
        if(dp[posK][ind] <= tmp){
            dp[posK][ind] = tmp;
            tambah[posK][ind] = l;
        }
    }
    //cout << endl;
}

void ternary_search_max(int posK, int ind){
    int l = posK-1,
        r = ind-1,
        m_ans = l;
    
    while(l <= r){        
        if(r-l <= 300){
            bruteforce_search(posK, ind, l, r);
            break;
        }

        ll  m1 = l + (r-l)/3,
            m2 = r - (r-l)/3;

//        cout << posK << " " << ind << ": " << m1 << " " << m2 << endl;
        
        ll  res1 = dp[posK-1][m1]+(pref[ind]-pref[m1])*suff[ind+1],
            res2 = dp[posK-1][m2]+(pref[ind]-pref[m2])*suff[ind+1];
        
        if(res1 > res2){
            r = m2-1;
            m_ans = m1;
        }else{
            l = m1+1;
            m_ans = m2;
        }
    }
    
//    cout <<  posK << " " << ind << ": " << m_ans << endl;
    
//    dp[posK][ind] = dp[posK-1][m_ans]+(pref[ind]-pref[m_ans])*suff[ind+1];
//    tambah[posK][ind] = m_ans;
}

void binser_max(int posK, int ind){
    int l = posK-1,
        r = ind-1,
        mid,
        m_ans = l;

    while(l < r){
        mid = (l+r)/2;
        ll  f1 = dp[posK-1][mid]+(pref[ind]-pref[mid])*suff[ind+1],
            f2 = dp[posK-1][mid+1]+(pref[ind]-pref[mid+1])*suff[ind+1];
        
        if(f1 > f2){
            r = mid+1;
            m_ans = mid;
        }else{
            l = mid;
            m_ans = mid+1;
        }
    }

    dp[posK][ind] = dp[posK-1][m_ans]+(pref[ind]-pref[m_ans])*suff[ind+1];
    tambah[posK][ind] = m_ans;
}

int main(){
    init();

    cin >> N >> K;
    
    for(int i=1;i<=N;i++){
        cin >> data[i];
        pref[i] = data[i]+pref[i-1];
    }
    
    for(int i=N;i>0;i--){
        suff[i] = suff[i+1]+data[i];
    }
   
    for(int j=1;j<N;j++){
        ll tmp = pref[j]*suff[j+1];
        //cout << j << " " << tmp << endl;    
        if(dp[1][j] <= tmp){
            dp[1][j] = tmp;
            tambah[1][j] = 0;
        }
    }
    
    for(int i=2; i<=K; i++){
        for(int j=1;j<N;j++){
            if(j < i) continue;
            //binser_max(i, j);
            if(abs(i-j) > 300) ternary_search_max(i, j);
            else bruteforce(i, j);
        }
    }

    for(int i=1;i<N;i++) ans = max(ans, dp[K][i]);
    
    int nxt,
        cnt = K;
    for(int i=N-1;i>0;i--){
        if(ans == dp[cnt][i]){
            putus.push(i);
            nxt = tambah[cnt][i];
            cnt--;
            break;
        }
    }
    while(nxt != 0){
        putus.push(nxt);
        nxt = tambah[cnt][nxt];
        cnt--;
    }
/*
    for(int i=1;i<=K;i++){
        for(int j=1;j<N;j++) cout << tambah[i][j] << " ";
        cout << endl;
    }
*/
    cout << ans << endl;
    
    cout << putus.top();
    putus.pop();
    while(!putus.empty()){
        cout << " " << putus.top();
        putus.pop();
    }
    cout << endl;
 
}

Compilation message (stderr)

sequence.cpp: In function 'void ternary_search_max(int, int)':
sequence.cpp:60:9: warning: variable 'm_ans' set but not used [-Wunused-but-set-variable]
         m_ans = l;
         ^~~~~

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