oj.uz

답안 #1087329

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1087329 2024-09-12T13:36:43 Z xnqs Bigger segments (IZhO19_segments) C++17
0 / 100
 0 ms 348 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <unordered_map>

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

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_cnt.count(cap)&&memo_cnt[cap]>=2) {
		return memo[cap];
	}
	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;
	memo[cap] = -0x3f3f3f3f;
	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));

	++memo_cnt[cap];
	return memo[cap] = std::max(memo[cap],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
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -