Submission #1270616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270616		duyanhchupapi	Feast (NOI19_feast)	C++20	4 / 100	1096 ms	10892 KiB

feast

#include <bits/stdc++.h>
using namespace std; using ll = long long; const int N = 300005;
int n, k, a[N];
ll dp[N][2], cnt[N][2];
// dp[i][1/0] co chon a[i] hay khong
// cnt[i][1/0] dem so doan da toa ra  
bool alien(ll P) {
	for(int i=1;i<=n;++i) {
		dp[i][0] = dp[i-1][0];
		cnt[i][0] = cnt[i-1][0];
		if(dp[i][0] < dp[i-1][1]) {
			dp[i][0] = dp[i-1][1];
			cnt[i][0] = cnt[i-1][1];
		}
		else if(dp[i][0] == dp[i-1][1]) cnt[i][0] = max(cnt[i][0], cnt[i-1][1]);
		dp[i][1] = dp[i][0] + a[i] - P;
		cnt[i][1] = cnt[i][0] + 1;
		if(dp[i][1] < dp[i-1][1] + a[i]) {
			dp[i][1] = dp[i-1][1] + a[i];
			cnt[i][1] = cnt[i-1][1];
		}
		else if(dp[i][1] == dp[i-1][1] + a[i]) cnt[i][1] = max(cnt[i][1], cnt[i-1][1]);
	}
	if(dp[n][1] > dp[n][0]) return (cnt[n][1] >= k);
	else if(dp[n][1] < dp[n][0]) return (cnt[n][0] >= k);
	else return (max(cnt[n][1], cnt[n][0]) >= k);
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k;
	for(int i=1;i<=n;++i) cin >> a[i];
	ll l = 0, r = 1e15, ans = 0; dp[0][1] = -1e18;
	while(l <= r) {
		int mid = (l+r)/2;
		if(alien(mid)) l = mid + 1, ans = mid;
		else r = mid - 1;
	}
	
	alien(ans);
	cout << max(dp[n][0], dp[n][1]) + k * ans;
	return 0;
}

• Subtask 1: 4 / 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