Submission #383209

#	Time	Username	Problem	Language	Result	Execution time	Memory
383209		maximath_1	Global Warming (CEOI18_glo)	C++11	28 / 100	2083 ms	3820 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]);

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

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

	return 0;
}

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