제출 #437572

#제출 시각아이디문제언어결과실행 시간메모리
437572soroush수열 (APIO14_sequence)C++17
71 / 100
2064 ms83664 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; int n, k; ll dp[maxn][2]; ll prt[maxn]; int par[maxn][207]; void solve(int k, int l = 1 , int r = n , int ul = 1 , int ur = n){ if(l > r)return; if(l == r){ for(int i = ul ; i <= ur and i < l ; i ++){ ll res = dp[i][!(k&1)]; res += (prt[l] - prt[i]) * (prt[n] - prt[l]); if(res > dp[l][k&1]){ dp[l][k&1] = res; par[l][k] = i; } } } int mid = (l + r) / 2; for(int i = ul ; i <= ur and i < mid ; i ++){ ll res = dp[i][!(k&1)]; res += (prt[mid] - prt[i]) * (prt[n] - prt[mid]); if(res >= dp[mid][k&1]){ dp[mid][k&1] = res; par[mid][k] = i; } } solve(k, l, mid - 1 , ul, par[mid][k]); solve(k, mid + 1 , r , par[mid][k], ur); } int32_t main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin >> n >> k; for(int i = 1 ; i <= n ; i ++) cin >> prt[i], prt[i] += prt[i - 1]; for(int i = 1 ; i <= k ; i ++) solve(i , i , n-1 , i-1 , n-1); int ans = 1; for(int i = 1 ; i <= n ; i ++)if(dp[i][k&1] > dp[ans][k&1])ans = i; cout << dp[ans][k&1] << endl; cout << ans; while(k > 1){ cout << ' ' << par[ans][k]; ans = par[ans][k] , k --; } 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...