oj.uz

Submission #944816

# Submission time Handle Problem Language Result Execution time Memory
944816 2024-03-13T06:04:52 Z Kaztaev_Alisher Feast (NOI19_feast) C++17
0 / 100
 30 ms 12280 KB 
#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 = 2e5+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;
	dp[0] = -INF;
	st.insert(0);
	for(ll i = 1; i <= n; i++){
		dp[i] = max(dp[i-1],a[i]+*st.rbegin()-md);
		st.insert(-a[i]+dp[i]);
	}
	return dp[n];
}
void solve(){
	cin >> n >> k;
	ll mx = -INF , mn = INF;
	for(ll i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
		if(a[i] > 0) mx = max(mx , a[i]);
		if(a[i] > 0) mn = min(mn , a[i]);
		a[i] += a[i-1];
	}
	ll ans = -INF;
	if(mx != -INF){
		ll l = mn , r = mx;
		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){
			ans = max(ans , get(l)+k*l);
			l++;
		}
	} else {
		mx = -INF , mn = INF;
		for(ll i = 1; i <= n; i++) {
			if(b[i] < 0) mx = max(mx , b[i]);
			if(b[i] < 0) mn = min(mn , b[i]);
		}
		ll l = mn , r = mx;
		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){
			ans = max(ans , get(l)+k*l);
			l++;
		}
	}
	cout << ans << "\n";
}
/*
*/
signed main(){
	ios;
	solve();
	return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 12124 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 11088 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 12280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 12124 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -