Submission #944858

#	Time	Username	Problem	Language	Result	Execution time	Memory
944858		Kaztaev_Alisher	Feast (NOI19_feast)	C++17	0 / 100	1031 ms	55120 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;
	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 = 100000000;
	while(r-l >= 10){
		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;
}

• 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