# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
963837 | kh0i | Feast (NOI19_feast) | C++17 | 370 ms | 26940 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;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll = long long;
using pii = pair<int, int>;
#define F first
#define S second
#define double long double
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
assert(l <= r);
return uniform_int_distribution<ll> (l, r)(rng);
}
const int N = 3e5 + 3;
const double eps = 1e-3;
int n;
pair<double, int> f[N][2];
double k, a[N];
pair<double, int> calc(double cost){
f[0][0] = {0, 0};
f[0][1] = {-1e15, 0};
for(int i = 1; i <= n; ++i){
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = max((pair<double, int>){f[i - 1][0].F + a[i] - cost, f[i - 1][0].S + 1}, pair<double, int>{f[i - 1][1].F + a[i], f[i - 1][1].S});
}
return max(f[n][0], f[n][1]);
}
void solve(){
cin >> n >> k;
for(int i = 1; i <= n; ++i)
cin >> a[i];
double l = 0, r = 1e15;
while(r - l > eps){
double mid = (l + r) / 2;
if(calc(mid).S >= k)
l = mid;
else
r = mid;
}
pair<double, int> res = calc(l);
cout << (ll)round(res.F + l * k);
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(0);
#define task "troll"
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int test = 1;
// cin >> test;
for(int i = 1; i <= test; ++i){
// cout << "Case #" << i << ": ";
solve();
}
#ifdef LOCAL
cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
#endif
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... |