// I will become better someday.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, int> pli;
typedef pair <int, ll> pil;
typedef pair <ll, ll> pll;
typedef pair <ld, ld> pdd;
#define debug(x) cout << '[' << #x << ": " << x << "] "
#define cio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define cases int _; cin >> _; while(_--)
#define pb push_back
#define eb emplace_back
#define space << " " <<
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define Unique(v) v.erase(unique(all(v)), v.end())
#define mset(x) memset(x, 0, sizeof(x))
#define sflush fflush(stdout)
#define cflush cout.flush()
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define lyes cout << "Yes\n"
#define lno cout << "No\n"
#define nl cout << "\n";
#define vt vector
#define ar array
#define uid uniform_int_distribution
template <typename T>
istream& operator >> (istream& in, vector<T>& a){
for(auto &x : a) in >> x;
return in;
}
template <typename T>
ostream& operator << (ostream& out, vector<T>& a){
for(auto &x : a) out << x << ' ';
return out;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
ll read(){
int w = 1, c;
ll ret;
while((c = getchar()) > '9' || c < '0'){
w = (c == '-' ? -1 : 1);
}
ret = c - '0';
while((c = getchar()) >= '0' && c <= '9'){
ret = ret * 10 + c - '0';
}
return ret * w;
}
ll rd(){
ll in;
cin >> in;
return in;
}
void write(ll x){
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9){
write(x / 10);
}
putchar(x % 10 + '0');
}
const int MAXN = 3e5 + 5, MAXM = 2e5 + 5, INF = 1e9 + 5, MOD = 1e9 + 7;
const ll LMOD = (ll) 1e18 + 9;
const ll LINF = 1e18 + 5;
const ld ep = 1e-8, Pi = acos(-1.0);
int n, m, k, x;
int a[MAXN];
string s;
pli solve(ll pen){
vt dp(n + 1, vt <ll> (2, 0));
vt cdp(n + 1, vt <int> (2, 0));
dp[0][1] = -pen;
cdp[0][1] = 1;
for(int i = 1; i <= n; ++i){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
if(dp[i][0] == dp[i - 1][0]) cdp[i][0] = max(cdp[i][0], cdp[i - 1][0]);
if(dp[i][0] == dp[i - 1][1]) cdp[i][0] = max(cdp[i][1], cdp[i - 1][1]);
dp[i][1] = max(dp[i - 1][0] + a[i] - pen, dp[i - 1][1] + a[i]);
if(dp[i][1] == dp[i - 1][0] + a[i] - pen) cdp[i][1] = max(cdp[i][1], cdp[i - 1][0] + 1);
if(dp[i][1] == dp[i - 1][1] + a[i]) cdp[i][1] = max(cdp[i][1], cdp[i - 1][1]);
}
return max((pli) {dp[n][0], cdp[n][0]}, (pli) {dp[n][1], cdp[n][1]});
}
void clear(){
}
int main(){
cio;
cin >> n >> k;
int cnt = 0;
ll sm = 0;
for(int i = 1; i <= n; ++i){
cin >> a[i];
// if(a[i] >= 0){
// ++cnt;
// sm += a[i];
// }
}
// if(cnt <= k){
// cout << sm << "\n";
// return 0;
// }
ll l = 0, r = 1e15, ans = 0;
while(l <= r){
ll mid = (l + r) >> 1;
auto res = solve(mid);
if(res.S >= k){
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
auto res = solve(ans);
cout << res.F + ans * k << "\n";
return 0;
}
# | 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... |