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>
using namespace std;
#define endl "\n"
#define pii pair<ll,ll>
#define sz second
#define val first
typedef long long int ll;
vector<pii> v;
int n,m;
vector<ll> available;
bool check(int ans){
int cadre=m-ans;
for(int i=0; i<n; i++) {
if(cadre<m&&v[i].sz<=available[cadre]) {
cadre++;
}
}
return (cadre==m);
}
int main()
{
ios_base:: sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
v.resize(n);
available.resize(m);
for(int i=0; i<n; i++) {
cin>>v[i].sz>>v[i].val;
}
sort(v.begin(),v.end());
for(int i=0; i<m; i++) {
cin>>available[i];
}
sort(available.begin(),available.end());
// first of all if it possible to fit k pictures then they would fit in the largest k frames
// so we will binary search on the answer k
int l=0;
int r=min(n,m);
int ans=0;
//cout<<check(1)<<endl;
while(l<=r) {
int mid=(l+r)/2;
if(check(mid)) {
ans=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
cout<<ans<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |