# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
166131 | ZwariowanyMarcin | 수열 (APIO14_sequence) | C++14 | 1792 ms | 81912 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, n) for(int i = 1; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cout << #x << " = " << x << endl
using namespace std;
const int nax = 1e5 + 111;
const long long inf = 1e18;
int n, k;
int a[nax];
ll dp[nax][2];
int opt[nax][202];
int pref[nax];
int ja, on, K;
void solve(int l, int r, int optl, int optr) {
if(l > r) return;
int m = (l + r) / 2;
for(int i = optl; i <= min(m, optr); ++i) {
ll w = dp[i - 1][on] + 1ll * (pref[m] - pref[i - 1]) * (pref[m] - pref[i - 1]);
if(w < dp[m][ja]) {
opt[m][K] = i;
dp[m][ja] = w;
}
}
solve(l, m - 1, optl, opt[m][K]);
solve(m + 1, r, opt[m][K], optr);
}
int main() {
scanf("%d %d", &n, &k);
k += 1;
for(int i = 1; i <= n; ++i) {
scanf("%d", a + i);
pref[i] = pref[i - 1] + a[i];
}
for(int i = 1; i <= n; ++i)
dp[i][0] = inf;
for(int i = 1; i <= k; ++i) {
K = i;
ja = i & 1;
on = !ja;
for(int j = 0; j <= n; ++j)
dp[j][ja] = inf;
solve(1, n, 1, n);
}
ll kwa = 1ll * pref[n] * pref[n];
printf("%lld\n", (kwa - dp[n][k & 1]) / 2);
vector <int> v;
int ind = n;
while(k > 1) {
assert(ind > 0);
assert(opt[ind][k] > 1);
v.pb(opt[ind][k]);
ind = opt[ind][k] - 1;
k -= 1;
}
reverse(v.begin(), v.end());
for(auto it : v)
printf("%d ", it - 1);
return 0;
}
컴파일 시 표준 에러 (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... |