# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
31964 | minimario | 수열 (APIO14_sequence) | C++11 | 0 ms | 1840 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000005;
typedef pair<int, int> pii;
#define f first
#define s second
pii line[MAX];
int orig[MAX];
double hit[MAX];
int ct = 0;
double sect(pii l1, pii l2) {
// l1.f * x + l1.s = l2.f * x + l2.s
return (double)(l2.s - l1.s) / (double)(l1.f - l2.f);
}
void add(int m, int b, int k) {
pii l = {m, b};
// l and line[2] > hit[2]
while (ct > 1 && sect(l, line[ct]) < hit[ct]) {
ct--;
}
ct++;
orig[ct] = k;
line[ct] = l;
if (ct != 1) { hit[ct] = sect(l, line[ct-1]); }
}
pii eval(int x) {
pii l; int ind = -1;
if (ct == 0) { return {0, 0}; }
if (ct == 1) {
l = line[1];
ind = orig[1];
}
else {
l = line[lower_bound(hit+2, hit+ct+1, (double)x) - hit - 1];
ind = orig[lower_bound(hit+2, hit+ct+1, (double)x) - hit - 1];
}
return {l.f * x + l.s, ind};
}
int a[MAX];
int p[MAX];
int dp[MAX][205];
int last[MAX][205];
int main() {
//freopen("a.in", "r", stdin);
//freopen("a.out", "w", stdout);
int n, k; scanf("%d %d", &n, &k);
for (int i=1; i<=n; i++) {
scanf("%d", &a[i]);
p[i] = p[i-1] + a[i];
}
for (int k=1; k<=n; k++) {
ct = 0;
for (int i=k-1; i<=n; i++) {
if (k == 1) {
dp[i][k] = 0;
}
else {
add(-p[i], -dp[i][k-1]+p[i]*p[i], i);
if (i != k-1) {
dp[i][k] = -eval(p[i]).f;
last[i][k] = eval(p[i]).s;
}
}
}
}
k++;
printf("%d\n", dp[n][k]);
while (k != 1) {
int bef = last[n][k];
printf("%d ", bef);
n = bef; k--;
}
}
컴파일 시 표준 에러 (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... |