Submission #995260

#	Time	Username	Problem	Language	Result	Execution time	Memory
995260		Yarema	Feast (NOI19_feast)	C++17	100 / 100	136 ms	1628 KiB

feast

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
typedef pair<db, int> PLI;

const LL INF = 1e12;

PLI f(VI& a, LL lambda)
{
	int n = SZ(a);
	PLI dp0 = {0, 0};
	PLI dp1 = {-INF, 0};
	FOR (i, 0, n)
	{
		PLI ndp0 = max(dp0, dp1);
		PLI ndp1 = max(PLI(dp0.F + a[i] - lambda, dp0.S + 1), PLI(dp1.F + a[i], dp1.S));
		
		dp0 = ndp0;
		dp1 = ndp1;
		//cerr << i << ' ' << dp0.F << ' ' << dp0.S << ' ' << dp1.F << ' ' << dp1.S << '\n';
	}
	return max(dp0, dp1);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, k;
	cin >> n >> k;
	VI a(n);
	FOR (i, 0, n)
		cin >> a[i];
	
	
	LL l = -1, r = INF;
	while (l + 1 < r)
	{
		LL m = (l + r) / 2;
		auto [val, cnt] = f(a, m);
		if (cnt > k)
			l = m;
		else
			r = m;
	}
	//cerr << r << '\n';
	auto [val, cnt] = f(a, r);
	cout << LL(val + cnt * r) << '\n';
	
	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