Submission #383229

#	Time	Username	Problem	Language	Result	Execution time	Memory
383229		maximath_1	Global Warming (CEOI18_glo)	C++11	55 / 100	55 ms	6024 KiB

glo

#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;
 
#define ll long long
#define ld long double
const int MX = 10005;
const int LG = (int)log2(MX) + 2;
const int BLOCK = 105;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
 
#define gc getchar//_unlocked //can't for window server
void cin(int &x){
	char c = gc(); bool neg = false;
	for(; c < '0'||'9' < c; c = gc())
		if(c == '-') neg=true;
	x = c - '0'; c = gc();
	for(; '0' <= c && c <= '9'; c = gc())
		x = (x << 1) + (x << 3) + (c - '0');
	if(neg) x = -x;
}

int LIS(vector<int> v){
	int sz = v.size();

	vector<int> dp;
	for(int i = 0; i < sz; i ++){
		auto it = lower_bound(dp.begin(), dp.end(), v[i]);
		if(it == dp.end()) dp.push_back(v[i]);
		else dp[it - dp.begin()] = v[i];
	}

	return dp.size();
}

int n, x;
vector<int> v;

int main(){
	cin(n); cin(x);
	v.resize(n);
	for(int i = 0; i < n; i ++)
		cin(v[i]);

	if(n <= 1000){
		int ans = -1;
		for(int j = n - 1; j >= 0; j --){
			v[j] += x;
			ans = max(ans, LIS(v));
		}

		printf("%d\n", ans);
	}else{
		if(x == 0) printf("%d\n", LIS(v));
		else{
			int ans = LIS(v);

			vector<int> pref(n), dp;
			for(int i = 0; i < n; i ++){
				auto it = lower_bound(dp.begin(), dp.end(), v[i]);
				if(it == dp.end()) dp.push_back(v[i]);
				else dp[it - dp.begin()] = v[i];
				pref[i] = dp.size();
			}

			vector<int> suff(n); dp.assign(n, 0);
			for(int i = n - 1; i >= 0; i --){
				int it = upper_bound(dp.begin(), dp.end(), v[i]) - dp.begin() - 1;
				dp[it] = v[i];
				suff[i] = n - it;
			}

			for(int i = 0; i < n - 1; i ++)
				ans = max(ans, pref[i] + suff[i + 1]);

			printf("%d\n", ans);
		}
	}

	return 0;
}

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