Submission #1271359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271359		duyanhchupapi	Feast (NOI19_feast)	C++20	100 / 100	110 ms	8656 KiB

feast

#include <bits/stdc++.h>
#define ll long long
using namespace std; const int N = 300005;
int n, k, a[N], cnt[N][2];
ll dp[N][2], inf = 1e18;
// 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-1][0] + a[i] - P;
        cnt[i][1] = cnt[i-1][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][0] > dp[n][1]) return cnt[n][0] >= k;
    else if(dp[n][0] < dp[n][1]) return cnt[n][1] >= k;
    else return max(cnt[n][0],cnt[n][1]) >= 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 = inf;
	dp[0][1] = -inf;
	while(l <= r) {
		ll mid = (l+r)/2;
		if(alien(mid)) l = mid + 1;
		else r = mid - 1;
	}
	r = max(0LL, r);
	alien(r);
	cout << max(dp[n][0], dp[n][1]) + r * k;
	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