Submission #433146

#TimeUsernameProblemLanguageResultExecution timeMemory
433146ngraceSplit the sequence (APIO14_sequence)C++14
39 / 100
2074 ms24268 KiB
#include <vector> #include <iostream> #include <utility> #include <deque> using namespace std; #define v vector #define pii pair<int,int> #define fi first #define se second #define ll long long int main(){ int N,K; cin>>N>>K; v<ll> vals(N); for(int i=0;i<N;i++) cin>>vals[i]; v<ll> prefix; prefix.push_back(vals[0]); for(int i=1;i<N;i++) prefix.push_back(prefix.back() + vals[i]); v<v<int>> from(K+2,v<int>(N+2,-1)); v<v<ll>> dp(K+2,v<ll>(N+2,0)); for(int k=1;k<=K;k++){ for(int i=k-1;i<N-1;i++){ ll val=0; int ind=0; for(int j=k-1;j<=i;j++){ if(j==0){ ll tmp=prefix[i] * (prefix[N-1]-prefix[i]); val=max(val,tmp); if(val==tmp) ind=j-1; continue; } ll tmp=prefix[i] * (prefix[N-1]-prefix[i]); tmp+=prefix[j-1]*prefix[i]; tmp+=dp[k-1][j-1] - prefix[N-1] * prefix[j-1]; val=max(val, tmp); if(val==tmp) ind=j-1; } dp[k][i]=val; from[k][i]=ind; } } ll out=0; int ind=0; for(int i=0;i<N;i++){ out=max(out, dp[K][i]); if(out==dp[K][i]) ind=i; } cout<<out<<endl; for(int k=K;k>0;k--){ cout<<ind+1<<" "; ind=from[k][ind]; } cout<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...