Submission #1273065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273065		goulthen	Feast (NOI19_feast)	C++20	0 / 100	30 ms	11888 KiB

feast

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second

const int MAXN = 3e5+10;
const int INF = 1e18+10;
int a[MAXN];

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
	int n,k; cin >> n >> k;
	rep(i,1,n) cin >> a[i];

	auto check = [&](int dx) {
		pii dp[n][2];

		dp[1][0] = {0,0};
		dp[1][1] = {a[1]-dx, 1};

		rep(i,2,n) {
			dp[i][0] = max(dp[i-1][0], dp[i-1][1]);

			dp[i][1] = max(pii(dp[i-1][0].fi + a[i]-dx, dp[i-1][0].se + 1),pii(dp[i-1][0].fi + a[i], dp[i-1][0].se));
		}

		return max(dp[n][0], dp[n][1]);
	};

	int lo = 0, hi = 1e18;
	while (lo < hi) {
		int mid = (lo+hi+1)/2;
		check(mid).se >= k ? lo =mid : hi = mid-1;
	}

	cout << check(lo).fi + lo*k;

	return 0;
}

• 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