Submission #944818

#	Time	Username	Problem	Language	Result	Execution time	Memory
944818		Kaztaev_Alisher	Feast (NOI19_feast)	C++17	0 / 100	1056 ms	19796 KiB

feast

#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;
	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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29