Submission #220230

#	Time	Username	Problem	Language	Result	Execution time	Memory
220230		kai824	Exhibition (JOI19_ho_t2)	C++17	100 / 100	84 ms	4476 KiB

joi2019_ho_t2

#include"bits/stdc++.h"
using namespace std;

pair<int,int> pics[100005];
int fs[100005];//frame size...

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,m,lo,hi,mid,ans=0;
    cin>>n>>m;
    for(int x=0;x<n;x++){
      cin>>pics[x].second>>pics[x].first;//size, value...
    }
    sort(pics,pics+n);//by increasing value, then by size...
    for(int x=0;x<m;x++){
      cin>>fs[x];
    }
    sort(fs,fs+m);
    for(int x=n-1;x>=0;x--){//only care about size of frame...
      //find smallest possible index of frame that can fit painting...
      if(pics[x].second>fs[m-1])pics[x].first=INT_MAX;
      else{
        lo=0;hi=m-1;
        while(lo<hi){
          mid=lo+(hi-lo)/2;
          if(pics[x].second<=fs[mid]){//picture fits in frame
            hi=mid;
          }else{
            lo=mid+1;//exceed frame size
          }
        }
        pics[x].first=lo;
      }
      pics[x].second=x+1;//the index to rmb...
      if(pics[x].first==INT_MAX)continue;
      if(ans>m-1-pics[x].first)continue;
      else ans++;//take the current thing...
    }
    cout<<ans;
    return 0;
}
/*
3 4
10 20
5 1
3 5
4 6 10 4
*/

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50