# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1212400 | huudai | Feast (NOI19_feast) | C++20 | 136 ms | 12348 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define BIT(x,i) (((x)>>(i))&1)
#define MASK(i) (1LL<<(i))
template<typename T1, typename T2> bool minimize(T1 &a, T2 b)
{if(a>b) a=b; else return 0; return 1;}
template<typename T1, typename T2> bool maximize(T1 &a, T2 b)
{if(a<b) a=b; else return 0; return 1;}
#define file "task"
const int maxn = 3e5 + 5;
const int MOD = 1e9 + 7;
const int oo = 1e9;
const ll OO = 1e18;
int n;
int k;
int a[maxn];
pll f[maxn][2];
void input(){
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
}
void dp(ll m){
memset(f, -0x3f, sizeof(f));
f[1][0] = mp(0, 0);
f[1][1] = mp(a[1] - m, 1);
for(int i = 1; i < n; i++){
maximize(f[i + 1][0], max(f[i][0], f[i][1]));
maximize(f[i + 1][1], mp(f[i][0].fi + a[i + 1] - m, f[i][0].se + 1));
maximize(f[i + 1][1], mp(f[i][1].fi + a[i + 1], f[i][1].se));
}
}
void proc(){
ll l = 0, r = (ll)1e15;
ll ans = 0;
while(l < r){
ll m = (l + r + 1) >> 1;
dp(m);
pll check = max(f[n][0], f[n][1]);
if(check.se >= k){
l = m;
} else r = m - 1;
}
dp(l);
cout << max(f[n][0], f[n][1]).fi + 1LL * l * k;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(0); cout.tie(nullptr);
if(fopen(file".inp", "r")){
freopen(file".inp", "r", stdin);
freopen(file".out", "w", stdout);
}
input();
proc();
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... |