This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long
using namespace std;
int pre, n, x;
vector<int> a;
int cnt(int idx) {
vector<int> temp=a, dp;
for(int i=0; i<n; i++) {
if(i<=idx) temp[i]-=x;
auto it=lower_bound(dp.begin(), dp.end(), temp[i]);
if(it==dp.end()) dp.push_back(temp[i]);
else *it=temp[i];
}
return dp.size();
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> x;
a.resize(n);
vector<int> dp;
for(int &p : a) {
cin >> p;
auto it=lower_bound(dp.begin(), dp.end(), p);
if(it==dp.end()) dp.push_back(p);
else *it=p;
}
pre=dp.size();
int l=0, r=n-1;
while(l<=r) {
int mid=l+r>>1;
int now=cnt(mid);
if(now>=pre) l=mid+1, pre=now;
else r=mid-1;
}
cout << pre << '\n';
return 0;
}
Compilation message (stderr)
glo.cpp: In function 'int main()':
glo.cpp:30:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int mid=l+r>>1;
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |