oj.uz

Submission #1107112

# Submission time Handle Problem Language Result Execution time Memory
1107112 2024-10-31T17:13:18 Z xnqs Triple Jump (JOI19_jumps) C++17
0 / 100
 79 ms 2420 KB 
// TODO implement optimally

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

int x, q;
int arr[500005];

int range_max_query(int l, int r) {
	int ret = 0;
	for (int i = l; i <= r; i++) {
		ret = std::max(ret,arr[i]);
	}
	return ret;
}

struct PQComp {
	bool operator() (int a, int b) {
		return arr[a] < arr[b];
	}
};

// take the 2 maxes, let their positions be 1 and 2
// therefore we have the following cases
//
// 1: ---1##--2
// 2: --###1--2
// 3: -1-2-####
int query(int l, int r) {
	if (r-l+1<=20) {
		int ret = 0;
		for (int i = l; i <= r; i++) {
			for (int j = i+1; j <= r; j++) {
				for (int k = j+(j-i); k <= r; k++) {
					ret = std::max(ret, arr[i]+arr[j]+arr[k]);
				}
			}
		}
		return ret;
	}

	std::priority_queue<int, std::vector<int>, PQComp> pq;
	for (int i = l; i <= r; i++) {
		pq.emplace(i);
	}

	std::vector<int> pos;
	while (!pq.empty()&&pos.size()<20) {
		int k = pq.top();
		pq.pop();
		pos.emplace_back(k);
	}

	int ret = 0;
	for (auto m1 : pos) {
		for (auto m2 : pos) {
			if (m1==m2) {
				continue;
			}

			if (m1>m2) std::swap(m1,m2);

			// 1
			for (int i = m1+1; std::abs(m1-i) <= std::abs(m2-i) && i <= r; i++) {
				//std::cout << m1 << " " << i << " " << m2 << " " << arr[m1]+arr[m2]+arr[i] << "\n";
				if (ret<arr[m1]+arr[m2]+arr[i]) {
					ret = arr[m1]+arr[m2]+arr[i];
				}
			}
			// 2
			for (int i = m1-1; std::abs(m1-i) <= std::abs(m1-m2) && i >= l; i--) {
				//std::cout << i << " " << m1 << " " << m2 << " " << arr[m1]+arr[m2]+arr[i] << "\n";
				if (ret<arr[m1]+arr[m2]+arr[i]) {
					ret = arr[m1]+arr[m2]+arr[i];
				}
			}
			// 3
			for (int i = m2+(m2-m1); i <= r; i++) {
				//std::cout << m1 << " " << m2 << " " << i << " " << arr[m1]+arr[m2]+arr[i] << "\n";
				if (ret<arr[m1]+arr[m2]+arr[i]) {
					ret = arr[m1]+arr[m2]+arr[i];
				}
			}
		}
	}

	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];
	}

	std::cin >> q;
	while (q--) {
		int l, r;
		std::cin >> l >> r;
		std::cout << query(l,r) << "\n";
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Incorrect 2 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Incorrect 2 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2256 KB Output is correct
2 Correct 19 ms 2256 KB Output is correct
3 Correct 68 ms 2300 KB Output is correct
4 Incorrect 79 ms 2420 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Incorrect 2 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -