Submission #1264466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264466		Alihan_8	Feast (NOI19_feast)	C++20	0 / 100	257 ms	12116 KiB

feast

#include <bits/stdc++.h>

using namespace std;

#define int long long

template <class F, class S>
bool chmax(F &x, const S &y){
	if ( x < y ){
		x = y;
		
		return true;
	}
	
	return false;
}

const int inf = 1e18;

signed main(){
	int n, k; cin >> n >> k;
	
	vector <int> a(n);
	
	for ( auto &u: a ) cin >> u;
	
	int cnt = 0;
	
	for ( auto &u: a ){
		if ( u >= 0 ) ++cnt;
	}
	
	k = min(k, cnt);
	
	int tmp;
	
	auto f = [&](int cost){
		vector <array<int,2>> dp(n + 1), fa(n + 1);
		
		for ( int i = 0; i <= n; i++ ) dp[i][1] = -inf;
		
		for ( int i = 1; i <= n; i++ ){
			if ( chmax(dp[i][0], dp[i - 1][0]) ) fa[i][0] = fa[i - 1][0];
			else if ( dp[i][0] == dp[i - 1][0] ) chmax(fa[i][0], fa[i - 1][0]);
			
			if ( chmax(dp[i][0], dp[i - 1][1]) ) fa[i][0] = fa[i - 1][1];
			else if ( dp[i][0] == dp[i - 1][1] ) chmax(fa[i][0], fa[i - 1][1]);
			
			if ( chmax(dp[i][1], dp[i - 1][1] + a[i - 1]) ) fa[i][1] = fa[i - 1][1];
			else if ( dp[i][1] == dp[i - 1][1] + a[i - 1] ) chmax(fa[i][1], fa[i - 1][1]);
			
			if ( chmax(dp[i][1], dp[i - 1][0] + a[i - 1] - cost) ) fa[i][1] = fa[i - 1][0] + 1;
			else if ( dp[i][1] == dp[i - 1][0] + a[i - 1] - cost ) chmax(fa[i][1], fa[i - 1][0] + 1);
			
			if ( chmax(dp[i][0], dp[i][1]) ) fa[i][0] = fa[i][1];
			else if ( dp[i][0] == dp[i][1] ) chmax(fa[i][0], fa[i][1]);
		}
		
		tmp = 0;
		
		int ans = 0;
		
		for ( int i = 1; i <= n; i++ ){
			if ( chmax(tmp, dp[i][1]) ) ans = fa[i][1];
			else if ( tmp == dp[i][1] ) chmax(ans, fa[i][1]);
		}
		
		return ans;
	};
	
	int l = -1e9, r = 1e9;
	
	while ( l < r ){
		int m = (l + r - 1) / 2;
		
		if ( f(m) <= k ) r = m;
		else l = m + 1;
	}
	
	f(l);
	
	cout << tmp + k * l << '\n';
}

• 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