Submission #441663

#	Time	Username	Problem	Language	Result	Execution time	Memory
441663		julian33	Split the sequence (APIO14_sequence)	C++14	50 / 100	2100 ms	32496 KiB

sequence

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
 
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}

const int mxN=1e4+5,mxK=205;

ll dp[mxN][mxK],go[mxN][mxK],psa[mxN],n,k;
vector<int> ans;
 
ll make(int at,int used){
    if(used==k || at==n)
        return 0;
    if(~dp[at][used])
        return dp[at][used];
    ll res=0; int best=at;
    for(int i=at;i<n;i++){
        if(make(i+1,used+1)+(psa[i]-psa[at-1])*(psa[n]-psa[i])>res){
            res=make(i+1,used+1)+(psa[i]-psa[at-1])*(psa[n]-psa[i]);
            best=i;
        }
    }
    go[at][used]=best;
    return dp[at][used]=res;
}

void construct(int at,int used){
    if(at==n || used==k)
        return;
    ans.pb(go[at][used]);
    construct(go[at][used]+1,used+1);
}

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    memset(dp,-1,sizeof(dp));
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>psa[i];
        psa[i]+=psa[i-1];
    }
    cout<<make(1,0)<<"\n";
    construct(1,0);
    for(int i=0;i<sz(ans);i++){
        cout<<ans[i]<<" \n"[i==sz(ans)-1];
    }
}

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