oj.uz

Submission #716622

# Submission time Handle Problem Language Result Execution time Memory
716622 2023-03-30T14:52:08 Z lamter Feast (NOI19_feast) C++17
4 / 100
 108 ms 8520 KB 
#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);
	});

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

	return 0-0;
}

Compilation message

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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 8268 KB Output is correct
2 Correct 97 ms 8392 KB Output is correct
3 Correct 108 ms 8520 KB Output is correct
4 Correct 93 ms 8468 KB Output is correct
5 Correct 92 ms 8416 KB Output is correct
6 Correct 99 ms 8240 KB Output is correct
7 Correct 94 ms 8280 KB Output is correct
8 Correct 97 ms 8444 KB Output is correct
9 Correct 94 ms 8288 KB Output is correct
10 Correct 95 ms 8340 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 8332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 8428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 8268 KB Output is correct
2 Correct 97 ms 8392 KB Output is correct
3 Correct 108 ms 8520 KB Output is correct
4 Correct 93 ms 8468 KB Output is correct
5 Correct 92 ms 8416 KB Output is correct
6 Correct 99 ms 8240 KB Output is correct
7 Correct 94 ms 8280 KB Output is correct
8 Correct 97 ms 8444 KB Output is correct
9 Correct 94 ms 8288 KB Output is correct
10 Correct 95 ms 8340 KB Output is correct
11 Incorrect 99 ms 8332 KB Output isn't correct
12 Halted 0 ms 0 KB -