Submission #258005

#	Time	Username	Problem	Language	Result	Execution time	Memory
258005		aggu_01000101	Split the sequence (APIO14_sequence)	C++14	0 / 100	59 ms	41208 KiB

sequence

#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <bits/stdc++.h>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define int long long
#define INF 10000000000000000
using namespace std;
#define mid(l, u) ((l+u)/2)
//#define cin fin
//#define cout fout
const int N = 100005;
const int K = 205;
int a[N];
int pref[N], suff[N];
int n, k;
int dp[N][K];
int nxt[N][K];
bool vis[N][K];
int f(int i, int j){
    if(i>n && j!=0) return -INF;
    if(j==0){
        nxt[i][j] = -1;
        return 0;
    }
    if(vis[i][j]) return dp[i][j];
    vis[i][j] = true;
    int amt = (suff[i]/(j+1));
    int l = i;
    int u = n - (j+1);
    int pt = i;
    while(l<=u){
        int m = mid(l, u);
        int qt = pref[m] - pref[i-1];
        if(qt <= amt){
            pt = max(pt, m);
            l = m+1;
        }
        else{
            u = m-1;
        }
    }
    //try pt
    int ans1 = f(pt+1, j-1) + ((pref[pt] - pref[i-1])*(suff[pt+1]));
    //try pt+1
    int ans2 = 0;
    if(pt+1 <= (n - (j+1))) ans2 = f(pt+2, j-1) + ((pref[pt+1] - pref[i-1])*(suff[pt+2]));
    //cout<<i<<" "<<j<<" ";
    if(ans1 > ans2){
        nxt[i][j] = pt;
    }
    else{
        nxt[i][j] = pt+1;
    }
    //cout<<nxt[i][j]<<endl;
    return dp[i][j] = max(ans1, ans2);
}
signed main(){
    //ofstream fin("2.in");
    //ofstream fout("2.out");
    cin>>n>>k;
    for(int i = 1;i<=n;i++) cin>>a[i];
    for(int i = 1;i<=n;i++) pref[i] = pref[i-1] + a[i];
    for(int i = n;i>=1;i--) suff[i] = suff[i+1] + a[i];
    cout<<f(1, k)<<endl;
    int nextind = 1;
    int currk = k;
    int lol = 0;
    while(lol<10 && nxt[nextind][currk]>0){
        cout<<nxt[nextind][currk]<<" ";
        nextind = nxt[nextind][currk] + 1;
        currk--;
        lol++;
    }
}
/*
7 3
4 1 3 4 0 2 3
 */

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