Submission #1101949

#TimeUsernameProblemLanguageResultExecution timeMemory
1101949TameGlobal Warming (CEOI18_glo)C++14
100 / 100
44 ms3536 KiB
#include <bits/stdc++.h> #define pu push #define pf push_front #define pb push_back #define pof pop_front #define pob pop_back #define fi first #define se second #define el cout<<"\n" #define ll long long #define ld long double #define MASK(i) (1LL<<(i)) #define BIT(x, i) (((x)>>(i))&1) #define SET_OFF(x, i) ((x)&~MASK(i)) #define SET_ON(x, i) ((x)|MASK(i)) #define c_bit(i) __builtin_popcount(i) const int MAX_SIZE = 200100; const int inf = (int)1e9+7; using namespace std; template<class T1, class T2> bool maximize(T1 &x, T2 y){if(x<y){x=y; return true;} return false;} template<class T1, class T2> bool minimize(T1 &x, T2 y){if(x>y){x=y; return true;} return false;} int nLength, nDist, res=0; int a[MAX_SIZE], Left[MAX_SIZE], Right[MAX_SIZE]; vector<int>dp; void init(){ cin>>nLength>>nDist; for (int i=0; i<nLength; i++){ cin>>a[i]; } } void ilovesunshine(){ init(); //find left dp.assign(nLength, inf); for (int i=0; i<nLength; i++){ int j = lower_bound(dp.begin(), dp.end(), a[i])-dp.begin(); dp[j]=a[i]; Left[i]=j+1; maximize(res, Left[i]); } //find right dp.assign(nLength, inf); for (int i=nLength-1; i>=0; i--){ int j = lower_bound(dp.begin(), dp.end(), -a[i]+nDist)-dp.begin(); Right[i]=j; int tmp = lower_bound(dp.begin(), dp.end(), -a[i]) - dp.begin(); dp[tmp]=-a[i]; } for (int i=0; i<nLength; i++) maximize(res, Left[i]+Right[i]); cout<<res; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("APEN.INP", "r", stdin); // freopen("APEN.OUT", "w", stdout); ilovesunshine(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...