Submission #1087482

#TimeUsernameProblemLanguageResultExecution timeMemory
1087482ThunnusSplit the sequence (APIO14_sequence)C++17
0 / 100
58 ms8792 KiB
#include<bits/stdc++.h> using namespace std; using i64 = long long; //#define int i64 #define vi vector<int> #define vvi vector<vi> #define vb vector<bool> #define pii pair<int, int> #define fi first #define se second #define sz(x) (int)(x).size() struct Line{ int m, c, i; Line(i64 _m, i64 _c, int _i) : m(_m), c(_c), i(_i) {} inline int calc(int x){ return m * x + c; } inline long double x_int(Line &other){ return (long double)(c - other.c) / (other.m - m); } }; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vi a(n + 1); for(int i = 1; i <= n; i++){ cin >> a[i]; a[i] += a[i - 1]; } vector<vector<i64>> dp(2, vector<i64>(n + 1)); vvi from(n + 1, vi(k + 2)); for(int j = 1; j <= k + 1; j++){ deque<Line> dq; dq.emplace_front(0, 0, 0); for(int i = 1; i <= n; i++){ int ps = a[n] - a[i]; while(sz(dq) >= 2 && dq.back().calc(ps) <= dq[sz(dq) - 2].calc(ps)){ dq.pop_back(); } dp[1][i] = dq.back().calc(ps) + a[i] * ps; from[i][j] = dq.back().i; Line cur = {-a[i - 1], dp[0][i - 1], i - 1}; while(sz(dq) >= 2 && cur.x_int(dq[0]) >= dq[1].x_int(dq[0])){ dq.pop_front(); } dq.emplace_front(cur); } dp[0] = dp[1]; } cout << dp[0][n] << "\n"; vi ind; for(int i = k + 1, idx = n; i >= 1; i--){ ind.emplace_back(idx); idx = from[idx][i]; } for(int i = sz(ind) - 1; i >= 1; i--){ cout << ind[i] << " "; } cout << "\n"; return 0; } // dp[i][j] = max(dp[z - 1][j - 1] + (a[i] - a[z - 1]) * (a[n] - a[i])) // dp[i][j] = max(-a[z - 1] * (a[n] - a[i]) + dp[z - 1][j - 1]) + a[i] * (a[n] - a[i])
#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...