Submission #1210052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210052		nmdminh	Feast (NOI19_feast)	C++20	100 / 100	161 ms	12152 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 = 3e5 + 5;
const ll INF = 1e18;

ll n, k;
ll a[N];
ii dp[N + 1][2];

ii check(ll lambda) {
	dp[0][0] = { 0, 0 };
	dp[0][1] = { a[0] - lambda, 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));
	}
	return max(dp[n - 1][0], dp[n - 1][1]);
}

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

	unsigned long long l = 0, r = INF;
	while (r > l) {
		ll mid = (l + r + 1) / 2;
		if (check(mid).second >= k)
			l = mid;
		else
			r = mid - 1;
	}
	ll res = check(l).first + k * l;
	cout << res;
}

• 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