Submission #383233

#TimeUsernameProblemLanguageResultExecution timeMemory
383233maximath_1Global Warming (CEOI18_glo)C++11
0 / 100
2088 ms163272 KiB
#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 = LIS(v); vector<int> suff(n), dp; 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; } dp.clear(); for(int i = 0; i < n; i ++){ for(int j : dp) printf("%d ", j); printf("\n"); int j = upper_bound(dp.begin(), dp.end(), v[i] + x - 1) - dp.begin(); ans = max(ans, j + suff[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]; } printf("%d\n", ans); 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...