제출 #916234

#제출 시각아이디문제언어결과실행 시간메모리
916234Alcabel수열 (APIO14_sequence)C++17
0 / 100
23 ms81780 KiB
#include <bits/stdc++.h> using namespace std; struct Line { long long a, b; int idx; Line() {} Line(long long _a, long long _b, int _idx) { a = _a, b = _b, idx = _idx; } long long f(int x) { return a * x + b; } ~Line() {} }; int sign(long long x) { if (x > 0) { return 1; } if (x < 0) { return -1; } return 0; } long long intersect(const Line& A, const Line& B) { // A.a * x + A.b = B.a * x + B.b // x = (B.b - A.b) / (A.a - B.a) long long numer = B.b - A.b, denom = A.a - B.a; int sn = sign(numer), sd = sign(denom); numer *= sn, denom *= sd; if (sn * sd == -1) { return numer / denom * (-1); } return (numer + denom - 1) / denom; } const int inf = 2e9; struct CHT { vector<long long> optX; vector<Line> lines; int ptr; CHT() { ptr = 0; } void clear() { optX.clear(); lines.clear(); ptr = 0; } void insert(const Line& l) { if (!lines.empty() && lines.back().a == l.a) { if (l.b >= lines.back().b) { return; } lines.pop_back(); optX.pop_back(); } while (!lines.empty() && intersect(lines.back(), l) <= optX.back()) { lines.pop_back(); optX.pop_back(); } if (!lines.empty()) { optX.emplace_back(intersect(lines.back(), l)); lines.emplace_back(l); } else { optX.emplace_back(-inf); lines.emplace_back(l); } } pair<long long, int> getVal(int x) { ptr = min(ptr, (int)lines.size() - 1); while (ptr + 1 < (int)lines.size() && optX[ptr + 1] <= x) { ++ptr; } assert(ptr < (int)lines.size()); return {lines[ptr].f(x), lines[ptr].idx}; } ~CHT() {} }; const int maxn = 1e5, maxk = 201; int par[maxn][maxk], dp[maxn][2]; void solve() { int n, k; cin >> n >> k; vector<int> a(n), pref(n + 1); for (int i = 0; i < n; ++i) { cin >> a[i]; pref[i + 1] = pref[i] + a[i]; } int layer = 0; for (int i = 0; i < n; ++i) { dp[i][0] = pref[i + 1] * 1ll * pref[i + 1]; par[i][0] = -1; } CHT cht; for (int g = 1; g <= k; ++g) { // cerr << "g: " << g << '\n'; layer ^= 1; cht.clear(); pair<long long, int> res; for (int i = g; i < n; ++i) { // cerr << "i: " << i << '\n'; cht.insert(Line(-2 * pref[i], dp[i - 1][layer ^ 1] + pref[i] * 1ll * pref[i], i - 1)); // cerr << "inserted!\n"; res = cht.getVal(pref[i + 1]); // cerr << "got!\n"; // cerr << "res: " << res.first + pref[i + 1] * 1ll * pref[i + 1] << '\n'; dp[i][layer] = res.first + pref[i + 1] * 1ll * pref[i + 1]; par[i][g] = res.second; } } cout << (pref[n] * 1ll * pref[n] - dp[n - 1][layer]) / 2 << '\n'; vector<int> ans; for (int i = n - 1, j = k; i >= 0 && j > 0; i = par[i][j], --j) { // cerr << "i: " << i << '\n'; // cerr << "par: " << par[i][j] << '\n'; ans.emplace_back(par[i][j] + 1); } reverse(ans.begin(), ans.end()); for (const int& x : ans) { cout << x << ' '; } cout << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); int T = 1; cin >> T; while (T--) { solve(); cerr << "-----------\n"; cout << "-----------\n"; } #else int T = 1; // cin >> T; while (T--) { solve(); } #endif 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...