제출 #958761

#제출 시각아이디문제언어결과실행 시간메모리
958761IWKR수열 (APIO14_sequence)C++17
60 / 100
299 ms131072 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int dp[201][100001]; int pre[100001]; int ind[201][100001]; struct cht { vector<pair<int, pair<int, int>>> v; int cur = 0; long double is(int a, int b, int c, int d) { return (long double)(d - b) / (a - c); } void add(int m, int c, int num) { if (v.size() && v.back().first == m && v.back().second.first > c) return; while (v.size() - cur > 1) { int s = v.size(); if ((v[s - 1].first == m && c > v[s - 1].second.first) || (is(v[s - 1].first, v[s - 1].second.first, m, c) <= is(v[s - 2].first, v[s - 2].second.first, m, c))) v.pop_back(); else break; } v.push_back({m, {c, num}}); } pair<int, int> query(int x) { while (v.size() - cur > 1) { if (v[cur].first * x + v[cur].second.first < v[cur + 1].first * x + v[cur + 1].second.first) cur++; else break; } return {v[cur].first * x + v[cur].second.first, v[cur].second.second}; } }; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) { int a; cin >> a; pre[i] = pre[i - 1] + a; } for (int i = 1; i <= k; i++) { cht hull; for (int j = i; j < n; j++) { if (i == 1) { dp[i][j] = pre[j] * (pre[n] - pre[j]); ind[i][j] = j; continue; } hull.add(pre[j - 1], dp[i - 1][j - 1], j - 1); pair<int, int> c = hull.query(pre[j] - pre[n]); dp[i][j] = c.first + pre[j] * pre[n] - pre[j] * pre[j]; ind[i][j] = c.second; } } pair<int, int> ans = {INT_MIN, INT_MIN}; for (int i = k; i <= n; i++) { ans = max(ans, {dp[k][i], i}); } cout << ans.first << '\n'; vector<int> v; int cur = ans.second; v.push_back(cur); for (int i = k; i >= 2; i--) { cur = ind[i][cur]; v.push_back(cur); } for (int i = k - 1; i >= 0; i--) { cout << v[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...