Submission #740249

#	Time	Username	Problem	Language	Result	Execution time	Memory
740249		josanneo22	수열 (APIO14_sequence)	C++17	0 / 100	2069 ms	16852 KiB

sequence

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

#define pb push_back
#define mp make_pair
#define fi first
#define se second

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,y;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=k;j++){
            if(dp[i][j]>=mx){
                mx=dp[i][j];
                x=i; y=j;
            }
        }
    }
    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());
    for(auto&x:ans) cout<<x<<' ';
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
}

Compilation message (stderr)

sequence.cpp: In function 'void solve()':
sequence.cpp:30:17: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |     int mx=-1,x,y;
      |                 ^

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