제출 #372285

#제출 시각아이디문제언어결과실행 시간메모리
372285Return_0수열 (APIO14_sequence)C++14
71 / 100
2096 ms9532 KiB
#pragma GCC optimize("O2") #include <bits/stdc++.h> using namespace std; typedef int ll; typedef long long lol; const ll N = 1e5 + 3, K = 201; ll par [K][N], n, k, cur, t; lol dp [2][N], ps [N]; void solve (ll l, ll r, ll optl, ll optr) { ll m = (l + r) >> 1, till = min(m, optl); ll bst = -1; lol mx = -1; for (ll i = m; i >= till; i--) { lol p = dp[t][i - 1] + ps[i - 1] * (ps[m] - ps[i - 1]); if (p > mx) mx = p, bst = i; } dp[1 - t][m] = mx; par[cur][m] = bst - 1; if (l == r) return; solve(l, m, optl, bst); solve(m + 1, r, bst, optr); } int main () { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>> n >> k; for (ll i = 1; i <= n; i++) cin>> ps[i], ps[i] += ps[i - 1]; for (cur = 1, t = 0; cur <= k; cur++, t ^= 1) solve(1, n, 1, n); cout<< dp[k & 1][n] << '\n'; cur = n; for (ll i = k; i > 0; --i) cur = par[i][cur], cout<< cur << ' '; 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...