Submission #90093

#	Time	Username	Problem	Language	Result	Execution time	Memory
90093		mra2322001	Split the sequence (APIO14_sequence)	C++14	50 / 100	212 ms	132096 KiB

sequence

#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 100002;

int n, a[N], k, pos[N][202];
ll f[N][202], t[N];

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> k;
    f1(i, n) cin >> a[i];
    f1(i, n) t[i] = t[i - 1] + a[i];

    f1(i, n) f[i][0] = (t[i])*1ll*(t[n] - t[i]);

    f1(i, n){
        f[i][0] = (t[i])*1ll*(t[n] - t[i]);
        for(int j = 1; j < i; j++){
            int now = 0;
            if(j > k) break;
            for(int x = i - 1; x >= 1; x--){
                now++;
                /// f[x][j - 1]
                if(x > j - 1){
                    ll cur = f[x][j - 1] + (t[i] - t[x])*(t[n] - t[i]);
                    f[i][j] = max(f[i][j], cur);
                    if(cur == f[i][j]){
                        pos[i][j] = x;
                    }
                }
                else break;
                if(now > 1000) break;
            }
        }
    }
    cout << f[n][k] << endl;
    int now = pos[n][k];
    while(k--){
        cout << now << " ";
        now = pos[now][k];
    }
}

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