제출 #1264465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264465		Alihan_8	Feast (NOI19_feast)	C++20	59 / 100	280 ms	16760 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;
}

__int128 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);
	
	inf = inf * inf * -1;
	
	__int128 tmp;
	
	auto f = [&](int cost){
		vector <array<__int128,2>> dp(n + 1);
		vector <array<int,2>> 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 = -1e15, r = 1e15;
	
	while ( l < r ){
		int m = (l + r - 1) / 2;
		
		if ( f(m) <= k ) r = m;
		else l = m + 1;
	}
	
	f(l);
	
	tmp += (__int128)k * l;
	
	int ans = tmp;
	
	cout << ans << '\n';
}

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