제출 #437585

#제출 시각아이디문제언어결과실행 시간메모리
437585soroush수열 (APIO14_sequence)C++11
0 / 100
16 ms1996 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2") #pragma GCC optimize("unroll-loops") #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[207][maxn]; 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[k][l] = 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[k][mid] = 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[k][ans] , 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...