제출 #989443

#제출 시각아이디문제언어결과실행 시간메모리
989443coldbr3w수열 (APIO14_sequence)C++17
0 / 100
54 ms131072 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<int, int>; #define pb push_back #define F first #define S second #define all(x) (x).begin(), (x).end() const ll N = 2e5 + 100; const ll inf = 1e18; const ll mod = 1e9 + 7; const ll block = 520; const ll base = 35711; ll n,k; ll a[N], mp[N], dp[N], lst[N], ps[N]; pll trace[N][210]; void compute(ll l, ll r, ll optl, ll optr, ll turn){ if(l > r) return; ll mid = (l + r) / 2; pll res = {-inf, -1}; for(int i = optl; i <= min(mid, optr);i++){ res = max(res, {lst[i - 1] + (ps[mid] - ps[i - 1]) * (ps[i-1]), i}); } trace[mid][turn] = {res.S - 1, turn - 1}; dp[mid] = res.F; ll opt = res.S; compute(l, mid - 1, optl, opt, turn); compute(mid + 1, r, opt, optr, turn); } /* 7 3 4 1 3 4 0 2 3 */ void to_nho_cau(){ cin >> n >> k; for(int i = 1; i <= n;i++){ cin >> a[i]; ps[i] = ps[i-1] + a[i]; } for(int j = 1; j <= k;j++){ compute(1, n, 1, n, j); for(int i = 0; i <= n;i++) lst[i] = dp[i], dp[i] = 0; } cout << lst[n] << '\n'; int i = n, j = k; while(j >= 1){ ll nxt_i = trace[i][j].F, nxt_j = trace[i][j].S; i = nxt_i, j = nxt_j; if(i >= 1) cout << i << " "; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while(t--) to_nho_cau(); }
#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...