Submission #949616

#	Time	Username	Problem	Language	Result	Execution time	Memory
949616		tnknguyen_	Split the sequence (APIO14_sequence)	C++14	28 / 100	92 ms	7260 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n' 
#define pii pair<int, int>

const int sz = 1e4 + 5;
long long a[sz], s[sz];
int n, k;

int f[1005][205], pre[1005][205];
namespace SUB123{
    bool ok(){
        return (n <= 200);
    }

    void solve(){
        // vector<vector<int>> f(n+5, vector<int>(k+5, 0));
        // vector<vector<int>> pre(n+5, vector<int>(k+5, -1));
        memset(pre, -1, sizeof pre);

        for(int j=1; j<=k; ++j){
            for(int i=1; i<=n; ++i){
                int L = 0, R = s[n] - s[i];
                for(int g=i; g>=j; --g){
                    L += a[g];
                    if(f[g-1][j-1] + (L * R) > f[i][j]){
                        f[i][j] = f[g-1][j-1] + (L * R);
                        pre[i][j] = g-1;
                    }
                }
            }
        }

        // for(int i=1; i<=n; ++i){
        //     for(int j=1; j<=k; ++j){
        //         cout<<f[i][j]<<' ';
        //     }
        //     cout<<endl;
        // }

        int ma = 0, p = -1;
        for(int i=n; i>=1; --i){
            if(f[i][k] > ma){
                ma = f[i][k];
                p = i;
            }
        }

        vector<int> v;
        int x = p;
        while(k >= 0){
            v.push_back(x);
            x = pre[x][k--];
        }
        
        v.pop_back();
        cout<<ma<<endl;
        while(v.size()){
            cout<<v.back()<<' ';
            v.pop_back();
        }

        //---------------------
        exit(0);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //freopen("main.inp","r",stdin);
    //freopen("main.out","w",stdout);

    cin>>n>>k;
    for(int i=1; i<=n; ++i){
        cin>>a[i];
        s[i] = s[i-1] + a[i];
    }

    SUB123::solve();

    return 0;
}

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