Submission #588046

#	Time	Username	Problem	Language	Result	Execution time	Memory
588046		Temmie	Feast (NOI19_feast)	C++17	100 / 100	612 ms	39744 KiB

feast

#include <bits/stdc++.h>

typedef std::pair <long long, int> pa;

int n, k;
std::vector <int> a;

std::vector <std::vector <pa>> dp;

pa g(long long l) {
	for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) dp[i][j] = { -1, -1 };
	auto f = [&] (auto&& self, int i, bool is) -> pa {
		if (i >= n) {
			return { 0, 0 };
		}
		if (dp[i][is].second != -1) {
			return dp[i][is];
		}
		dp[i][is] = self(self, i + 1, false);
		pa cand = self(self, i + 1, true);
		cand.second += !is;
		cand.first += a[i];
		cand.first -= l * !is;
		dp[i][is] = std::max(dp[i][is], cand);
		return dp[i][is];
	};
	return f(f, 0, false);
}

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	std::cin >> n >> k;
	dp.resize(n, std::vector <pa> (2));
	a.resize(n);
	for (int& x : a) {
		std::cin >> x;
	}
	long long l = 0, r = 1LL << 42, ans = 0;
	while (l <= r) {
		long long mid = (l + r) >> 1;
		pa val = g(mid);
		if (val.second > k) {
			l = mid + 1;
		} else {
			r = mid - 1;
			ans = val.first + mid * k;
		}
	}
	std::cout << ans << "\n";
	
}

• 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