Submission #716624

#	Time	Username	Problem	Language	Result	Execution time	Memory
716624		lamter	Feast (NOI19_feast)	C++17	0 / 100	123 ms	16884 KiB

feast

#define INPFILE "FEAST.INP"
#define OUTFILE "FEAST.OUT"

#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
using lli = long long int;
template <class X, class Y> inline bool maximise(X& a, Y b) { return a < b ? a = b, true : false; }

template <class T, class F>
T BINARY_SEARCH(T l, T r, const F& f) {
	T ans = r + 1;
	while (l <= r) {
		T m = (l + r) >> 1;

		bool upd;
		int status;

		tie(upd, status) = f(m);

		if (upd)
			ans = m;

		if (status == 0)
			return ans;

		if (status == -1)
			r = m - 1;

		if (status == +1)
			l = m + 1;
	}
	return ans;
}

const int MAX = 3e5 + 5;
const lli INF = 1e14;

int N, K;
int a[MAX];

lli dp[MAX][2];
int cnt[MAX][2];

int solve(lli cost) {
	for (int j : {0, 1}) {
		fill(dp[j], dp[j] + N + 1, -INF);
		fill(cnt[j], cnt[j] + N + 1, 0);
	}

	dp[0][0] = 0;
	dp[0][1] = -INF;

	for (int i = 0; i < N; i++) {
		int x = a[i + 1];

		if (dp[i][0] > -INF) {
			if (maximise(dp[i + 1][0], dp[i][0]))
				cnt[i + 1][0] = cnt[i][0];
			if (maximise(dp[i + 1][1], dp[i][0] + x - cost))
				cnt[i + 1][1] = cnt[i][0] + 1;
		}

		if (dp[i][1] > -INF) {
			if (maximise(dp[i + 1][0], dp[i][1]))
				cnt[i + 1][0] = cnt[i][1];
			if (maximise(dp[i + 1][1], dp[i][1] + x))
				cnt[i + 1][1] = cnt[i][1];
		}
	}

	return cnt[N][max_element(dp[N], dp[N] + 2) - dp[N]];
}

int main(void) {
	if (fopen(INPFILE, "r")) {
		freopen(INPFILE, "r", stdin);
		freopen(OUTFILE, "w", stdout);
	}

	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];

	lli cost = BINARY_SEARCH(0LL, +INF, [&] (lli x) -> pair <bool, int> {
		int acum = solve(x);

		if (acum == K)
			return mp(true, 0);

		if (acum <= K)
			return mp(true, -1);

		if (acum > K)
			return mp(false, +1);

		assert(0);
	});

	assert(solve(cost) == K);

	lli ans = *max_element(dp[N], dp[N] + 2) + K * cost;
	cout << ans << '\n';

	return 0-0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:77:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   freopen(INPFILE, "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
feast.cpp:78:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   freopen(OUTFILE, "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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