Submission #1209993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209993		nmdminh	Feast (NOI19_feast)	C++20	0 / 100	229 ms	21320 KiB

feast

#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <random>
#include <algorithm>
#include <ctype.h>
#include <sstream>
#include <stack>
#include <map>
#include <queue>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <functional>
using namespace std;
#define endl '\n' 
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> ii;
typedef vector<ii> vll;
const ll lim = 1e9 + 7;
const int N = 3 * 1e5 + 5;
const ll INF = 1e9 * 300000;

ll n, k;
ll a[N];
pair<long double, int> dp[N + 1][2];

bool check(long double lambda) {
	dp[0][0] = { 0, 0 };
	dp[0][1] = { -INF, 0 };

	for (ll i = 1; i <= n; i++) {
		dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
		dp[i][1] = max(make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second),
			make_pair(dp[i - 1][0].first + a[i] - lambda, dp[i - 1][0].second + 1));
	}
	if (max(dp[n][1], dp[n][0]).second >= k)
		return 1;
	else
		return 0;
}

int main() {
	cin >> n >> k;
	for (ll i = 1; i <= n; i++)
		cin >> a[i];

	long double l = 0, r = INF;
	while (r > l + 0.1) {
		long double mid = (l + r) / 2;
		if (check(mid))
			l = mid;
		else
			r = mid;
	}
	check(l);
	cout << round(l * k + max(dp[n][1], dp[n][0]).first);
}

• 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