Submission #1145086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145086		am_aadvik	Global Warming (CEOI18_glo)	C++20	100 / 100	76 ms	2936 KiB

glo

#include <iostream>
#include<vector>
#include<algorithm>
const int inf = 2e9 + 5;
using namespace std;

int main() {
	int n, x, ans = 1; cin >> n >> x;
	vector<int> a(n);
	for (auto& v : a) cin >> v;

	vector<int> arr(n, inf), res(n);
	for (int i = 0; i < n; ++i) {
		auto pos = lower_bound(arr.begin(), arr.end(), a[i]) - arr.begin();
		arr[pos] = a[i], res[i] = pos + 1;
	}

	arr.assign(n, inf);
	for (int i = n - 1; i >= 0; --i)
		ans = max(ans, res[i] + (int)(lower_bound(arr.begin(), arr.end(), -a[i] + x) - arr.begin())),
		arr[lower_bound(arr.begin(), arr.end(), -a[i]) - arr.begin()] = -a[i];

	cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25