제출 #72924

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72924		duckmoon99	Global Warming (CEOI18_glo)	C++14	42 / 100	96 ms	5748 KiB

glo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e18
#define ret return

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll a[222222];
ll b[222222];
int ans1[222222];
int ans2[222222];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    ll x;
    cin >> n >> x;
    for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	if(n<=50 && x<=50){
		int tans=-1;
		for(int l = 0; l < n; l++){
			for(int r = l+1; r <= n; r++){
				for(int d = -x; d <= x; d++){
					for(int i = 0; i < n; i++){
						b[i]=a[i];
					}
					for(int i = l; i < r; i++){
						b[i]+=d;
					}
					vector<ll> dd(n+1,INF);
					for(int i = 0; i < n; i++){
						*lower_bound(dd.begin(),dd.end(),b[i])=b[i];
					}
					for(int i = 0; i <= n; i++){
						if(dd[i]==INF){
							tans=max(tans,i);
							i=n+1;
						}
					}
				}
			}
		}
		cout << tans;
		ret 0;
	}
	else if(x==0){
		vector<ll> dd(n+1,INF);
		for(int i = 0; i < n; i++){
			*lower_bound(dd.begin(),dd.end(),a[i])=a[i];
		}
		for(int i = 0; i <= n; i++){
			if(dd[i]==INF){
				cout << i;
				ret 0;
			}
		}
	}
	else{
		vector <ll> LIS;
		for(int i = 0; i < n; i++){
			if(LIS.empty()){
				LIS.pb(a[i]);
			}
			else{
				if(LIS[LIS.size()-1]<a[i]){
					LIS.pb(a[i]);
				}
				else{
					*lower_bound(LIS.begin(),LIS.end(),a[i])=a[i];
				}
			}
			ans1[i]=LIS.size();
		}
		vector <ll> LISS;
		for(int i = 0; i < n; i++){
			if(LISS.empty()){
				LISS.pb(-a[n-1-i]);
			}
			else{
				if(LISS[LISS.size()-1]<-a[n-1-i]){
					LISS.pb(-a[n-1-i]);
				}
				else{
					*lower_bound(LISS.begin(),LISS.end(),-a[n-1-i])=-a[n-1-i];
				}
			}
			ans2[n-i-1]=LISS.size();
		}
		int tans = max(ans2[0],ans1[n-1]);
		/*for(int i = 0; i < n; i++){
			cout << '*' << ans2[i] << endl;
		}*/
		for(int i = 0; i < n-1; i++){
			tans=max(tans,ans1[i]+ans2[i+1]);
		}
		cout << tans;
	}
}

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