Submission #1209988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209988		nmdminh	Feast (NOI19_feast)	C++20	0 / 100	218 ms	21324 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 + 1;	

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