Submission #815413

#	Time	Username	Problem	Language	Result	Execution time	Memory
815413		Mirali7	Feast (NOI19_feast)	C++17	100 / 100	153 ms	10596 KiB

feast

#include <iostream>
#include <string>
#include <deque>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <fstream>
#include <stack>
#include <cmath>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <random>
#include <array>
#include <chrono>
#include <functional>
#include <numeric>
#include <complex>
using namespace std;

#define ll long long
#define ld long double
#define ull uint64_t
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fst first
#define snd second

#define forn(i, n) for (int i = 1; i <= n; i++)
#define dforn(i, a, b) for (int i = a; i <= b; i++) 
#define rforn(i, n) for (int i = n; i >= 1; i--)
#define rdforn(i, a, b) for (int i = b; i >= a; i--)
#define sforn(i, a, b, s) for (ll i = a; i <= b; i += s)
#define aforn(v, a) for (auto& v : a)

const int mod = 998244353;
const ld pi = acos(-1);
const ll N = 1e6;
const ll inf = 1e17;
const int iinf = 1 << 30;
const ld dinf = 1e10;
const double eps = 1e-10;

void solve() {
	ll n, k;
	cin >> n >> k;
	vector<ll> a(n + 1);
	forn(i, n) {
		cin >> a[i];
	}
	auto calc = [&](ll lambda) {
		vector<ll> dp(n + 1), cnt(n + 1);
		ll best = 0, bcnt = 1;
		forn(i, n) {
			dp[i] = dp[i - 1];
			cnt[i] = cnt[i - 1];
			best += a[i];
			if (best - lambda > dp[i]) {
				dp[i] = best - lambda;
				cnt[i] = bcnt;
			}
			if (dp[i] > best) {
				best = dp[i];
				bcnt = cnt[i] + 1;
			}
		}
		return make_pair(dp[n], cnt[n]);
	};
	ll l = -1, r = 1e13;
	while (r - l > 1) {
		ll m = (l + r) >> 1;
		pll f = calc(m);
		if (f.snd <= k) {
			r = m;
		}
		else {
			l = m;
		}
	}
	pll cur = calc(r);
	ll ans = cur.fst + k * r;
	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.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