Submission #1266516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266516		pcheloveks	Feast (NOI19_feast)	C++20	100 / 100	103 ms	7480 KiB

feast

#define _CRT_SECURE_NO_WARNINGS

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize ("O3")

//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")

//Babahnineeleven will win IOI 2040
//Tanya Zadniprovska will win EGOI 2025
//Andrew Holod will NOT win IOI 2025
//Andrew Holod did not qualify to IOI 2025))))))))))
//Andrew Pavlyk is best coder in Khmelnytskiiii

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cstring> // �л� memset

using namespace std;

#define endl '\n'

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef std::pair <ll, ll> pii;
typedef std::pair <ll, ull> piu;
typedef std::pair <ld, ld> pdd;

const ll DIM = 300007;
const ld PI = 3.14159265358979;
const ll SQDIM = 460;
const ll MXMASK = (1 << 20);
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ld eps = 0.00000000001;
const ll Bits = 32;
const ll Bsize = 300;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

FILE* stream;

ll n, k;
ll a[DIM];

bool operator<(pii p1, pii p2) {
	if (p1.first != p2.first) return p1.first < p2.first;
	return p1.second > p2.second;
}

pii solve(ll p) {
	vector < pii > F(n + 1);

	pii mxF = { 0, 0 };
	pii best = { 0, 0 };

	for (int i = 1; i <= n; i++) {
		F[i] = max(F[i - 1], { best.first + a[i] - p, best.second + 1 });

		mxF = max(F[i], mxF);
		best = max(best, { mxF.first - a[i], mxF.second });
	}
	return F[n];
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifdef _DEBUG
	freopen_s(&stream, "input.txt", "r", stdin);
	freopen_s(&stream, "output.txt", "w", stdout);
#endif

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

	ll L = 0, R = INF;
	while (R - L > 1) {
		ll mid = (L + R) >> 1;
		if (solve(mid).second <= k) R = mid;
		else L = mid;
	}

	cout << solve(R).first + solve(R).second * R << endl;

	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