Submission #1087312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087312		xnqs	Bigger segments (IZhO19_segments)	C++17	13 / 100	32 ms	7040 KiB

segments

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <unordered_map>

const int BULAN = 50;
int x;
int arr[500005];
int64_t pfx[500005];
std::unordered_map<int64_t,std::unordered_map<int,int>> memo;

inline int64_t sum_query(int l, int r) {
	return pfx[r] - pfx[l-1];
}

int solve(int64_t cap, int pos = x) {
	if (memo.count(cap)&&memo[cap].count(pos)) {
		return memo[cap][pos];
	}
	if (pos==0) {
		return 0;
	}
	if (arr[pos]>cap) {
		return -0x3f3f3f3f;
	}

	int i = pos+1;
	int64_t sum = 0;
	int ret = -0x3f3f3f3f;
	int cnt = 0;
	while (i-1>=1&&sum+arr[i-1]<=cap) {
		--i;
		sum += arr[i];

		++cnt;
		if (cnt<=BULAN) {
			ret = std::max(ret,1+solve(sum,i-1));
		}
	}

	ret = std::max(ret,1+solve(sum,i-1));

	return memo[cap][pos] = ret;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x;
	for (int i = 1; i <= x; i++) {
		std::cin >> arr[i];
		pfx[i] = pfx[i-1] + arr[i];
	}

	/*for (int cap = 1; cap <= 50; cap++) {
		std::cout << cap << " " << solve(cap) << "\n";
	}*/

	const auto bs = [&]() {
		int ret = 1;
		int64_t l = 1, r = 1000000000000000000;
		while (l<=r) {
			int64_t m = (l+r)/2;
			int tmp = solve(m);
			if (tmp!=-0x3f3f3f3f) {
				ret = std::max(ret,tmp);
				r = m-1;
			}
			else {
				l = m+1;
			}
		}
		return ret;
	};

	std::cout << bs() << "\n";
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27