Submission #740293

#	Time	Username	Problem	Language	Result	Execution time	Memory
740293		josanneo22	Split the sequence (APIO14_sequence)	C++17	28 / 100	2082 ms	32468 KiB

sequence

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

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define int long long
void solve(){
    int n,k; cin>>n>>k;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<int> pre(n+1);
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
    vector<vector<int>> dp(n+1,vector<int>(k+1,-1e9)),from(n+1,vector<int>(k+1,-1)); 
    for(int i=0;i<=n;i++) dp[i][0]=0;
    for(int i=0;i<=k;i++) dp[0][i]=0;
    for(int i=0;i<=n;i++){ 
        for(int j=0;j<=i;j++){
            for(int s=k;s>=1;s--){
                if(dp[j][s-1]!=-1e9){
                    if(dp[j][s-1]+(pre[i]-pre[j])*(pre[n]-pre[i])>dp[i][s]){
                        dp[i][s]=dp[j][s-1]+(pre[i]-pre[j])*(pre[n]-pre[i]);
                        from[i][s]=j;
                    }
                }
            }
        }
    }
    int mx=-1,x=0,y=0;
    for(int i=0;i<=n;i++){
        if(dp[i][k]>mx){
            mx=dp[i][k];
            x=i; y=k;
        }
    }
    cout<<mx<<'\n';
    vector<int> ans;
    for(int i=y;i>=1;i--){
        ans.pb(x);
        x=from[x][i];
    }
    reverse(ans.begin(),ans.end());
    if(ans.size()<k-1){
        for(int i=1;i<=k;i++){
            cout<<i<<' ';
        }
    }
    else{
        for(auto&x:ans) cout<<x<<' ';
    }
}
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
}

Compilation message (stderr)

sequence.cpp: In function 'void solve()':
sequence.cpp:44:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   44 |     if(ans.size()<k-1){
      |        ~~~~~~~~~~^~~~

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