Submission #1021751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021751		ef10	Global Warming (CEOI18_glo)	C++17	100 / 100	82 ms	6284 KiB

glo

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

#define LL long long

LL N, X;
LL A[200005];
LL PR[200005];
LL dp[200005];

int main() {
	cin >> N >> X;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
	LL res = 0;
	dp[1] = A[1];
	LL E = 2;
	for (int i = 2; i <= N; i++) {
		int ind = lower_bound(dp+1,dp+E,A[i])-dp;
		PR[i]=ind;
		res = max(res,PR[i]);
		dp[ind] = A[i];
		if (ind==E) {
			E++;
		}
	}
	dp[1]=-A[N];
	E=2;
	for (int i = N-1; i>=1; i--) {
		int ind = lower_bound(dp+1,dp+E,X-A[i])-dp;
		res = max(res,PR[i]+ind-1);

		ind = lower_bound(dp+1,dp+E,-A[i])-dp;
		dp[ind]=-A[i];
		if (ind == E) {
			E++;
		}
	}
	cout << res << endl;
}

• 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