Submission #48567

#	Time	Username	Problem	Language	Result	Execution time	Memory
48567		faishol27	Split the sequence (APIO14_sequence)	C++14	0 / 100	20 ms	1788 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pi;
typedef long long ll;

#define fi first
#define se second

const int MAXN = 1e5+5;

int N, K;
int data[MAXN], pref[MAXN], suff[MAXN];
ll ans=0;
bool putus[MAXN];

pi hitung(int l, int r){
    pi ret = {-1, -1}; //{indeks putus, score}
    
    for(int i=l+1; i<r-1; i++){
        int tmp = -1;

        tmp = (pref[i]-pref[l])*(suff[i+1]-suff[r+1]);
        //cout << "R: " <<  i << " " << tmp << endl;
        if(tmp > ret.se){
            ret.fi = i;
            ret.se = tmp;
        }
    }

    return ret;
}

int main(){
    memset(data, 0, MAXN);
    memset(pref, 0, MAXN);
    memset(suff, 0, MAXN);
    memset(putus, 0, MAXN);

    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];
    }
    
    putus[N] = 1;

    for(int i=0;i<K;i++){
        int l=0, r=0;
        pi tmp, optimal;
        
        //cout << "==== " << i << " ====\n";

        for(int j=1;j<=N;j++){
            if(putus[j]){
                l = r;
                r = j;
                
            //    cout << l << " " <<  r << endl;
                
                tmp = hitung(l, r);

                if(optimal.se < tmp.se){
                    optimal = tmp;
                } 
            }
        }

        ans += optimal.se;
        putus[optimal.fi] = 1;
    }

    cout << ans << endl;

    int cnt=0;
    for(int i=1;i<=N;i++){
        if(putus[i]){
            cout << i;
            cnt++;

            if(cnt==K){
                cout << endl;
                break;
            }else cout << " ";
        }   
    }
}

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