Submission #944874

#	Time	Username	Problem	Language	Result	Execution time	Memory
944874		Kaztaev_Alisher	Feast (NOI19_feast)	C++17	100 / 100	117 ms	15304 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 = 300000000000000 ,  mod = 1e9+7 , P = 6547;	
 
ll n , k , a[N];
pair<ll,ll> dp[N][2];
ll get(ll md){
	dp[0][0] = {0,0};
	dp[0][1] = {-INF,0};
	for(ll i = 1; i <= n; i++){
		dp[i][0] = max(dp[i-1][0] , dp[i-1][1]);
		pair<ll,ll> c = {dp[i-1][0].F+md+a[i] , dp[i-1][0].S+1};
		pair<ll,ll> b = {dp[i-1][1].F+a[i] , dp[i-1][1].S};
		dp[i][1] = max(c , b);
	}
	return (max(dp[n][0],dp[n][1]).S >= k);
}
void solve(){
	cin >> n >> k;
	for(ll i = 1; i <= n; i++) cin >> a[i];
	ll l = -INF , r = 0 , res = 0;
	while(l <= r){
		ll md = (l+r) >> 1;
		if(get(md)){
			res = md;
			r = md-1;
		} else {
			l = md+1;
		}
	}
	get(res);
	cout << max(dp[n][1].F , dp[n][0].F)-res*k << "\n";
}
/*
*/
signed main(){
	ios;
	solve();
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29