| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 439943 | dongliu0426 | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 300000
#define INF 0x3f3f3f3f3f3f3f3f
int n, k, a[N + 1];
pair<long double, int> dp[N + 1][2];
template<class T, class U> T lastTrue(T lo, T hi, U f) {
assert(lo <= hi); --lo; /* assuming f is decreasing */
while (lo < hi) { /* find last index such that f is true */
T mid = lo + (hi - lo + 1) / 2;
f(mid) ? lo = mid : hi = mid - 1;
} return lo;
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
auto check = [&](long double penalty) {
dp[0][0] = {0, 0}, dp[0][1] = {-INF, 0};
for (int i = 1; i <= n; ++i) {
pair<long double, int> last = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][0] = max(make_pair(last.first - penalty, last.second + 1), last);
dp[i][1] = max(make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second),
make_pair(dp[i - 1][0].first + a[i] - penalty, dp[i - 1][0].second + 1));
}
return max(dp[n][0], dp[n][1]).second >= k;
};
long double lower = 0, upper = INF;
for (int it = 0; it < 100; ++it) {
long double mid = (lower + upper) / 2;
if (check(mid)) {
lower = mid;
} else {
upper = mid;
}
}
long double penalty = lower;
check(penalty);
printf("%lld\n", (long long) round(penalty * k + max(dp[n][0], dp[n][1]).first));
}