제출 #647044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
647044		google	수열 (APIO14_sequence)	C++17	0 / 100	2085 ms	16540 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int szn = 10001,szk=201;
int dp[szn][szk],arr[szn],pre[szn],n,k;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 0;i<n;i++) {
        cin >> arr[i];
        pre[i] = arr[i];
        if (i) pre[i] += pre[i-1];
    }
    memset(dp,0,sizeof(dp));
    for (int c = 1;c<=k;c++){
        for (int i = c;i<n;i++){
            for (int j = 0;j<i;j++){
                dp[i][c] = max(dp[i][c],dp[j][c-1]+(pre[j]*(pre[i]-pre[j])));
            }
        }
    }
    cout << dp[n-1][k] << '\n';
    int t = n-1, c = k;
    vector<int> ans;
    for (int i = n-2;~i;i--){
        if (dp[t][c] == dp[i][c-1]+pre[i]*(pre[t]-pre[i])){
            ans.push_back(i+1);
            t = i;
            c--;
        }
        if (!c) break;
    }
    for (int i = ans.size()-1;~i;i--) cout << ans[i] << ' ';
    return 0;
}

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