제출 #1265256

#제출 시각아이디문제언어결과실행 시간메모리
1265256canhnam357수열 (APIO14_sequence)C++20
100 / 100
953 ms87512 KiB
#include <bits/stdc++.h> #define int long long #define sqr(x) ((x) * (x)) #define MASK(i) (1LL << (i)) using namespace std; const int inf = 1e18; // y = a * x + b struct Line { int a; int b; }; bool operator < (Line a, Line b) { return true; } int lower_divide(int a, int b) { return a / b; } int upper_divide(int a, int b) { return (a+b-1) / b; } // Duoc dat trong comment la dao chieu hull struct Hull { vector<int> pos; vector<int> trace; vector<Line> lines; Hull(Line first, int id) { pos.emplace_back(-inf); // pos.emplace_back(inf); lines.emplace_back(first); trace.emplace_back(id); } // Them duong thang voi a tang dan // Trong comment: them duong thang voi a giam dan void update(Line l, int id) { int A = l.a; int B = l.b; if(A == lines.back().a) { return; } while(true) { int A1 = lines.back().a; int B1 = lines.back().b; int X1 = pos.back(); // A * X + B == A1 * X + B1 int intersect = lower_divide(B - B1, A1 - A); // int intersect = upper_divide(B - B1, A1 - A); if(intersect <= X1) { // if(intersect >= X1) { pos.pop_back(); lines.pop_back(); trace.pop_back(); } else { pos.push_back(intersect); lines.push_back({A, B}); trace.emplace_back(id); break; } } } int pre_p = 0; int query(int X) { int p = lower_bound(pos.begin(), pos.end(), X) - pos.begin() - 1; // int p = lower_bound(pos.begin(), pos.end(), X, greater<int>()) - pos.begin() - 1; pre_p = p; Line l = lines[p]; return l.a * X + l.b; } int query_trace(int X) { return trace[pre_p]; } }; int32_t trace[201][100001]; int32_t main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif srand(time(0)); ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<int> a(n+1); for(int i = 1; i <= n; i++) cin >> a[i]; vector<int> pre = a; for(int i = 1; i <= n; i++) pre[i] += pre[i-1]; vector<int> dp(n+1); vector<int> dp_cur(n+1); for(int i = 0; i <= n; i++) { dp[i] = sqr(pre[i]); trace[0][i] = 0; } for(int j = 1; j <= k; j++) { Hull hull({-2 * pre[j], dp[j] + sqr(pre[j])}, j); for(int i = j+1; i <= n; i++) { int X = pre[i]; dp_cur[i] = hull.query(X) + sqr(X); trace[j][i] = hull.query_trace(X); int new_A = -2 * pre[i]; int new_B = dp[i] + sqr(pre[i]); hull.update({new_A, new_B}, i); } swap(dp, dp_cur); } int ans = (sqr(pre[n]) - dp[n]) / 2; cout << ans << "\n"; vector<int> block; int pos = n; for(int j = k; j > 0; j--) { block.push_back(trace[j][pos]); pos = trace[j][pos]; } reverse(block.begin(), block.end()); for(int i : block) cout << i << " "; cout << "\n"; }
#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...