oj.uz

Submission #1087305

# Submission time Handle Problem Language Result Execution time Memory
1087305 2024-09-12T13:23:39 Z xnqs Bigger segments (IZhO19_segments) C++17
13 / 100
 1500 ms 2492 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

const int BULAN = 5;
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

# Verdict Execution time Memory 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 208 ms 2492 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 232 ms 2492 KB Output is correct
12 Correct 17 ms 2392 KB Output is correct
13 Correct 34 ms 2396 KB Output is correct
14 Correct 183 ms 2396 KB Output is correct
15 Correct 4 ms 2396 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory 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 208 ms 2492 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 232 ms 2492 KB Output is correct
12 Correct 17 ms 2392 KB Output is correct
13 Correct 34 ms 2396 KB Output is correct
14 Correct 183 ms 2396 KB Output is correct
15 Correct 4 ms 2396 KB Output is correct
16 Execution timed out 1581 ms 2396 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory 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 208 ms 2492 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 232 ms 2492 KB Output is correct
12 Correct 17 ms 2392 KB Output is correct
13 Correct 34 ms 2396 KB Output is correct
14 Correct 183 ms 2396 KB Output is correct
15 Correct 4 ms 2396 KB Output is correct
16 Execution timed out 1581 ms 2396 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory 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 208 ms 2492 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 232 ms 2492 KB Output is correct
12 Correct 17 ms 2392 KB Output is correct
13 Correct 34 ms 2396 KB Output is correct
14 Correct 183 ms 2396 KB Output is correct
15 Correct 4 ms 2396 KB Output is correct
16 Execution timed out 1581 ms 2396 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory 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 208 ms 2492 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 232 ms 2492 KB Output is correct
12 Correct 17 ms 2392 KB Output is correct
13 Correct 34 ms 2396 KB Output is correct
14 Correct 183 ms 2396 KB Output is correct
15 Correct 4 ms 2396 KB Output is correct
16 Execution timed out 1581 ms 2396 KB Time limit exceeded
17 Halted 0 ms 0 KB -