# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
853295 | chanhchuong123 | 수열 (APIO14_sequence) | C++14 | 398 ms | 90656 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define task ""
const long long INF = 1e18 + 0702;
const int MAX = 100010;
int n, k;
int a[MAX];
int pf[MAX];
int trace[MAX][202];
long long dp[2][MAX];
struct Line {
int m; long long c; int id;
Line(int _m = 0, long long _c = 0, int _id = 0) {
m = _m;
c = _c;
id = _id;
}
long long eval(long long x) {
return m * x + c;
}
};
struct ConvexHullTrick {
vector<Line> lines;
int pt = 0;
bool bad(const Line &l1, const Line &l2, const Line &l3) {
return 1LL * (l1.c - l3.c) * (l2.m - l1.m) <= 1LL * (l1.c - l2.c) * (l3.m - l1.m);
}
void add(long long m, long long c, int id) {
if (lines.size() && lines.back().m == m) {
long long maxC = c;
while (lines.size() && lines.back().m == m) {
maxC = max(maxC, lines.back().c);
lines.pop_back();
}
lines.push_back(Line(m, maxC, id));
return;
}
Line line(m, c, id); while (lines.size() >= 2 && bad(lines[lines.size() - 2], lines.back(), line)) lines.pop_back();
lines.push_back(line); pt = min(pt, int(lines.size()) - 1);
}
pair<long long, int> get(int x) {
if (lines.size() == 1) return make_pair(lines[0].eval(x), lines[0].id); while (pt + 1 < lines.size() && lines[pt + 1].eval(x) >= lines[pt].eval(x)) ++pt;
return make_pair(lines[pt].eval(x), lines[pt].id);
}
} cht[2];
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> n >> k; ++k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
pf[i] = pf[i - 1] + a[i];
}
memset(dp, -1, sizeof dp);
dp[0][0] = 0;
long long res = 0;
for (int j = 1; j <= k; ++j) {
int prv = (j - 1) & 1, cur = j & 1;
cht[prv].lines.clear();
cht[prv].pt = 0;
memset(dp[cur], -1, sizeof dp[cur]);
for (int i = j; i <= n; ++i) {
if (dp[prv][i - 1] > -1) cht[prv].add(pf[i - 1], -1LL * pf[i - 1] * pf[i - 1] + dp[prv][i - 1], i - 1);
pair<long long, int> ans = cht[prv].get(pf[i]);
if (i == n && j == k) res = ans.first;
dp[cur][i] = ans.first;
trace[i][j] = ans.second;
}
}
cout << res << '\n';
vector<int> posAns;
do {
n = trace[n][k--];
posAns.push_back(n);
} while (k > 1);
for (int &id: posAns) {
cout << id << ' ';
}
return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |