oj.uz

Submission #944858

# Submission time Handle Problem Language Result Execution time Memory
944858 2024-03-13T06:45:49 Z Kaztaev_Alisher Feast (NOI19_feast) C++17
0 / 100
 1000 ms 55120 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 = 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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1008 ms 55120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1029 ms 23632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1031 ms 23792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1008 ms 55120 KB Time limit exceeded
2 Halted 0 ms 0 KB -