Submission #1210862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210862		THXuan	Feast (NOI19_feast)	C++20	100 / 100	766 ms	23912 KiB

feast

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define INF 1e9
using namespace std; 
typedef long long ll;
const ll MAXN = 100005;

pair<ll, ll>f(ll mid, vector<ll>& v, ll n) {
	vector<vector<pair<ll, ll>>>dp(n, vector<pair<ll, ll>>(2));
	dp[0][0] = { 0, 0 };
	dp[0][1] = { v[0] - mid, 1 };
	for (int i = 1; i < n; i++) {
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
		pair<ll, ll>x = { dp[i - 1][0].first + v[i] - mid, dp[i - 1][0].second + 1 };
		pair<ll, ll>y = { dp[i - 1][1].first + v[i], dp[i - 1][1].second};
		dp[i][1] = max(x, y);
	}
	return max(dp[n - 1][0], dp[n - 1][1]);
}

void solve()
{
	int n, k; cin >> n >> k;
	vector<ll>v(n);
	for (int i = 0; i < n; i++)cin >> v[i];
	ll lo = 0; ll hi = 1e15;
	while (lo < hi) {
		ll mid = (lo + hi + 1) / 2;
		if (f(mid, v, n).second >= k)lo = mid;
		else hi = mid - 1;
	}
	pair<ll, ll>ans = f(lo, v, n);
	cout << ans.first + lo * k << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;// cin >> t;
	while (t--) solve();
	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