#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const ll N = 3e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7 , P = 6547;
ll n , k , a[N] , dp[N] , b[N];
ll get(ll md){
set<ll> st;
map<ll,ll> p;
dp[0] = -k*md;
st.insert(dp[0]);
p[0] = 0;
for(ll i = 1; i <= n; i++){
dp[i] = max(dp[i-1],a[i]+*st.rbegin()-md);
ll nw = p[dp[i-1]]+1;
ll j = -a[i]+dp[i-1];
if(!p.count(j)) p[j] = nw;
else p[j] = min(p[j] , nw);
if(p[j] < k) st.insert(-a[i]+dp[i-1]);
nw = p[*st.rbegin()]+1;
j = *st.rbegin()-md;
if(!p.count(j)) p[j] = nw;
else p[j] = min(p[j] , nw);
if(p[j] < k) st.insert(-a[i]+a[i]+*st.rbegin()-md);
}
// cout << "\n";
return dp[n];
}
void solve(){
cin >> n >> k;
for(ll i = 1; i <= n; i++) {
cin >> a[i];
a[i] += a[i-1];
}
ll ans = -INF;
ll l = 0 , r = 100000000000000;
while(r-l >= 100){
ll mdl = l+(r-l)/3;
ll mdr = r-(r-l)/3;
ll resl = get(mdl)+k*mdl;
ll resr = get(mdr)+k*mdr;
ans = max(ans , resl);
ans = max(ans , resr);
if(resl < resr){
l = mdl;
} else {
r = mdr;
}
}
while(l <= r){
ll resl = get(l)+k*l;
ans = max(ans , resl);
l++;
}
cout << ans << "\n";
}
/*
*/
signed main(){
ios;
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1035 ms |
50804 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1036 ms |
23280 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1035 ms |
23736 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1035 ms |
50804 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |