# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1112898 | KhoaHo | Feast (NOI19_feast) | C++17 | 137 ms | 15180 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define task "test"
#define pb push_back
#define SZ(a) (a).begin(), (a).end()
#define SZZ(a, Begin, End) (a) + (Begin), (a) + (Begin) + (End)
#define BIT(a) (1LL << (a))
#define vec vector
#define fi first
#define se second
#define mp make_pair
#define MASK(x, i) (((x) >> (i))&1)
typedef long long ll;
typedef pair<ll, ll> ii;
template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b, 1) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b, 1) : 0); }
void fastio() {
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
if (fopen(task ".inp", "r")) {
freopen(task ".inp", "r", stdin);
freopen(task ".out", "w", stdout);
}
else if (fopen(task ".in", "r")) {
freopen(task ".in", "r", stdin);
freopen(task ".out", "w", stdout);
}
}
const int N = int(3e5) + 100;
const ll INF = 1e18;
int n, k;
ll a[N];
ii dp[N][2];
void init() {
cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> a[i];
}
// dp(i, 0) = dp(i - 1, 0) + a
ii calc(ll C) {
dp[1][0] = ii(0, 0);
dp[1][1] = ii(a[1] - C, 1);
for(int i = 2; i <= n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max(ii(dp[i - 1][0].fi + a[i] - C, dp[i - 1][0].se + 1),
ii(dp[i - 1][1].fi + a[i], dp[i - 1][1].se));
}
return max(dp[n][0], dp[n][1]);
}
void process(const int &tc) {
ll l = 0, r = 1e18;
ll ans = 0;
while(l <= r) {
ll mid = l + (r - l)/2;
if(calc(mid).se <= k) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
ii res = calc(ans);
cout << res.fi + res.se * ans;
}
int main() {
fastio();
int t = 1;
//cin >> t;
for (int i = 1; i <= t; i++) {
init();
process(i);
}
return 0;
}
Compilation message (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... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |