oj.uz

답안 #1087308

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

const int BULAN = 4;
int x;
int arr[500005];
int64_t pfx[500005];

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

int solve(int64_t cap, int pos = x) {
	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 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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 202 ms 2484 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2392 KB Output is correct
11 Correct 222 ms 2396 KB Output is correct
12 Correct 16 ms 2396 KB Output is correct
13 Correct 30 ms 2396 KB Output is correct
14 Correct 179 ms 2396 KB Output is correct
15 Correct 4 ms 2392 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 202 ms 2484 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2392 KB Output is correct
11 Correct 222 ms 2396 KB Output is correct
12 Correct 16 ms 2396 KB Output is correct
13 Correct 30 ms 2396 KB Output is correct
14 Correct 179 ms 2396 KB Output is correct
15 Correct 4 ms 2392 KB Output is correct
16 Execution timed out 1555 ms 2396 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 202 ms 2484 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2392 KB Output is correct
11 Correct 222 ms 2396 KB Output is correct
12 Correct 16 ms 2396 KB Output is correct
13 Correct 30 ms 2396 KB Output is correct
14 Correct 179 ms 2396 KB Output is correct
15 Correct 4 ms 2392 KB Output is correct
16 Execution timed out 1555 ms 2396 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 202 ms 2484 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2392 KB Output is correct
11 Correct 222 ms 2396 KB Output is correct
12 Correct 16 ms 2396 KB Output is correct
13 Correct 30 ms 2396 KB Output is correct
14 Correct 179 ms 2396 KB Output is correct
15 Correct 4 ms 2392 KB Output is correct
16 Execution timed out 1555 ms 2396 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 202 ms 2484 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2392 KB Output is correct
11 Correct 222 ms 2396 KB Output is correct
12 Correct 16 ms 2396 KB Output is correct
13 Correct 30 ms 2396 KB Output is correct
14 Correct 179 ms 2396 KB Output is correct
15 Correct 4 ms 2392 KB Output is correct
16 Execution timed out 1555 ms 2396 KB Time limit exceeded
17 Halted 0 ms 0 KB -