Submission #48662

#	Time	Username	Problem	Language	Result	Execution time	Memory
48662		faishol27	Split the sequence (APIO14_sequence)	C++14	0 / 100	52 ms	24816 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;
 
// f(x,y) = score
// x = pemotongan ke-x
// y = indeks pemotongan
//
//
 
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 ternary_search_max(int posK, int ind){
    int l = posK-1,
        r = ind-1,
        m_ans;
    
    while(l <= r){
        ll m1 = l + (r-l)/3,
            m2 = l + ceil(double(r-l)*2/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 if(res1 < res2){
            l = m1+1;
            m_ans = m2;
        }else{
            m_ans = m1;
            break;
        }
    }
    
//    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;
}

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;

            ternary_search_max(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:66:60: warning: 'm_ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dp[posK][ind] = dp[posK-1][m_ans]+(pref[ind]-pref[m_ans])*suff[ind+1];
                                                  ~~~~~~~~~~^

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