제출 #110876

#제출 시각아이디문제언어결과실행 시간메모리
110876aleksam수열 (APIO14_sequence)C++14
33 / 100
298 ms132096 KiB
//Apio 14 sequence #include <bits/stdc++.h> #define INF INT_MAX #define MOD 100000007 #define MAX_N 100005 #define MAX_K 205 using namespace std; int N, K, a[MAX_N]; long long dp[MAX_K][MAX_N]; int sc[MAX_K][MAX_N]; int main(){ ios::sync_with_stdio(false); cin>>N>>K; for(int i=0; i<N; ++i){ cin>>a[i]; } long long s=0; for(int i=N-1; i>=0; --i){ s+=a[i]; dp[0][i]=s*s; sc[0][i]=N; } for(int k=1; k<=K; ++k){ s=a[N-k-1]; dp[k][N-k-1]=dp[k-1][N-k]+s*s; sc[k][N-k-1]=N-k; int scc=N-k; for(int i=N-k-2; i>=0; --i){ s+=a[i]; while( (scc>i+1 && (s-a[scc-1])*(s-a[scc-1])+dp[k-1][scc-1] <= s*s+dp[k-1][scc] ) || (scc>i+2 && (s-a[scc-1]-a[scc-2])*(s-a[scc-1]-a[scc-2])+dp[k-1][scc-2] <= s*s+dp[k-1][scc]) || (scc>i+3 && (s-a[scc-1]-a[scc-2]-a[scc-3])*(s-a[scc-1]-a[scc-2]-a[scc-3])+dp[k-1][scc-3] <= s*s+dp[k-1][scc]) || (scc>i+4 && (s-a[scc-1]-a[scc-2]-a[scc-3]-a[scc-4])*(s-a[scc-1]-a[scc-2]-a[scc-3]-a[scc-4])+dp[k-1][scc-4] <= s*s+dp[k-1][scc]) ){ scc--; s-=a[scc]; } dp[k][i]=s*s+dp[k-1][scc]; sc[k][i]=scc; } } s=0; for(int i=0; i<N; ++i)s+=a[i]; cout<<(s*s-dp[K][0])/2<<endl; int cur=0; for(int i=0; i<K; ++i){ cout<<sc[K-i][cur]<<" "; cur=sc[K-i][cur]; } return 0; } /* 7 3 4 1 3 4 0 2 3 */
#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...