Submission #732564

#	Time	Username	Problem	Language	Result	Execution time	Memory
732564		ac2hu	Split the sequence (APIO14_sequence)	C++14	28 / 100	2079 ms	104948 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 1e5 + 10;
const int K = 200 + 10;
int n, k, a[N], dp[N][K], b[N][K];
signed main(){
    iostream::sync_with_stdio(false);cin.tie(nullptr);
    cin >> n >> k;
    for(int i = 1;i<=n;i++)cin >> a[i];
    for(int i = 1;i<=n;i++)a[i] += a[i - 1];
    for(int l = 1;l<=k;l++){
        for(int i = 1;i<=n;i++){
            for(int j = i - 1;j>=min(1ll, l - 1);j--){
                int C = (a[i] - a[j])*a[j] + dp[j][l - 1];
                if(C >= dp[i][l])dp[i][l] = C, b[i][l] = j;
            }
        }
    }
    cout << dp[n][k] << "\n";
    vector<int> v = {n}; 
    for(int l = k;l>=1;l--){
        v.push_back(b[v.back()][l]);
    }
    reverse(v.begin(), v.end());v.pop_back();reverse(v.begin(), v.end());
    for(int e : v)cout << e << " ";
    cout << "\n";
}

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