제출 #515919

#제출 시각아이디문제언어결과실행 시간메모리
515919jk410수열 (APIO14_sequence)C++17
28 / 100
2062 ms2636 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF=9e18; int N,K; int Prev[201][1001]; ll A[1001],DP[201][1001]; stack<int> S; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>N>>K; for (int i=1; i<=N; i++){ cin>>A[i]; A[i]+=A[i-1]; } for (int t=1; t<=K; t++){ for (int i=1; i<=N; i++){ for (int j=1; j<=i; j++){ if (DP[t][i]<DP[t-1][j]+(A[i]-A[j])*A[j]){ DP[t][i]=DP[t-1][j]+(A[i]-A[j])*A[j]; Prev[t][i]=j; } } } } cout<<DP[K][N]<<"\n"; for (int t=K,i=N; t; t--){ if (!Prev[t][i]) break; if (Prev[t][i]!=i) S.push(Prev[t][i]); i=Prev[t][i]; } while (!S.empty()){ cout<<S.top()<<" "; S.pop(); } return 0; }
#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...