# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
29754 | sampriti | 수열 (APIO14_sequence) | C++14 | 19 ms | 88532 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
struct line {
long long m, c;
line(long long _m, long long _c) : m(_m), c(_c) {};
long long at(long long x) {
return m * x + c;
}
double intersect(line other) {
return double(other.c - c)/(m - other.m);
}
};
int N, K;
int A[100001];
long long P[100001];
long long dp[2][100002];
int nxt[202][100002];
vector<pair<line, int> > lines;
vector<double> inter;
void insert(line x, int k) {
while(!inter.empty() && x.intersect(lines.back().first) <= inter.back()) {
inter.pop_back();
lines.pop_back();
}
if(!lines.empty()) {
inter.push_back(x.intersect(lines.back().first));
}
lines.push_back({x, k});
}
int inter_ptr;
pair<line, int> get_best(long long x) {
inter_ptr = min(inter_ptr, (int)inter.size());
while(inter_ptr < inter.size() && x > inter[inter_ptr]) inter_ptr++;
return lines[inter_ptr];
}
int main() {
scanf("%d %d", &N, &K);
for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
for(int i = 1; i <= N; i++) P[i] = P[i - 1] + A[i];
dp[0][0] = LLONG_MIN/2;
int t = 1;
for(int _k = 2; _k <= K + 1; _k++) {
dp[t][0] = LLONG_MIN/2;
lines.clear();
inter.clear();
inter_ptr = 0;
for(int i = 1; i <= N; i++) {
insert(line(P[i - 1], dp[t ^ 1][i - 1] - P[i - 1] * P[i - 1]), i);
auto it = get_best(P[i]);
dp[t][i] = it.first.at(P[i]);
nxt[_k][i] = it.second;
}
t ^= 1;
}
printf("%lld\n", dp[t ^ 1][N]);
int i = N, j = K + 1;
while(j > 1) {
printf("%d ", nxt[j][i] - 1);
i = nxt[j][i] - 1;
j--;
}
printf("\n");
}
컴파일 시 표준 에러 (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... |