| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1356937 | pqhxapple | Aliens (IOI16_aliens) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = (0), _n = (n); i < _n; ++i)
#define MASK(x) (1LL << (x))
#define ON(mask, i) (((mask) >> (i)) & (1LL))
#define ALL(x) begin(x), end(x)
#define el cout << '\n'
template <class X, class Y> inline bool maximize(X &x, const Y &y) { return (x < y) ? x = y, 1 : 0; }
template <class X, class Y> inline bool minimize(X &x, const Y &y) { return (x > y) ? x = y, 1 : 0; }
constexpr int MAXN = 3e5 + 10;
int n, k;
int a[MAXN];
void load_input(void)
{
cin >> n >> k;
FOR(i, 1, n) cin >> a[i];
}
pair <long long, int> dp[MAXN][2];
pair <long long, int> calc(long long lmb)
{
dp[1][0] = make_pair(0, 0);
dp[1][1] = make_pair(a[1] - lmb, 1);
FOR(i, 2, n)
{
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max(make_pair(dp[i - 1][0].first + a[i] - lmb, dp[i - 1][0].second + 1),
make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
}
return max(dp[n][0], dp[n][1]);
}
void process(void)
{
long long low = 0, high = 1e18;
while (low <= high)
{
long long mid = (low + high) >> 1LL;
calc(mid).second >= k ? low = mid + 1 : high = mid - 1;
}
cout << calc(high).first + high * k << '\n';
}
signed main(void)
{
cin.tie(nullptr)->sync_with_stdio(false);
cin.exceptions(cin.failbit);
#define task "E"
if (fopen(task".INP", "r"))
{
freopen(task".INP", "r", stdin);
freopen(task".OUT", "w", stdout);
}
int testcase = 1;
while (testcase--)
{
load_input();
process();
}
return 1 ^ 1;
}