Submission #927280

#	Time	Username	Problem	Language	Result	Execution time	Memory
927280		belgianbot	Global Warming (CEOI18_glo)	C++14	100 / 100	54 ms	5460 KiB

glo

#include <bits/stdc++.h>

using namespace std;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N, X; cin >> N >> X;
	
	vector <int> a (N);
	for (int i(0); i < N; i++)
		cin >> a[i];
	
	vector <int> pre(N), dp(N, INT_MAX);
	for (int i(0); i < N; i++) {
		auto it = lower_bound(dp.begin(), dp.end(), a[i] + X);
		int index = distance(dp.begin(), it);
		pre[i] = index;
		
		it = lower_bound(dp.begin(), dp.end(), a[i]);
		*it = a[i];
	}
	int ans(0);
	vector <int> suf(N, 0);
	for (int i(N - 1); i >= 0; i--) {
		int l(0), r(N - i), pos;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (suf[mid] > a[i]) l = mid + 1;
			else {
				pos = mid;
				r = mid - 1;
			}
		}
		suf[pos] = a[i];
		ans = max(ans, pre[i] + pos + 1);
	}
	
	cout << ans << '\n';
		
	return 0;
}
			

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:36:25: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |   ans = max(ans, pre[i] + pos + 1);

• 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