Submission #1153268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153268		zhasyn	Exhibition (JOI19_ho_t2)	C++20	50 / 100	1096 ms	3396 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1e5 + 100, M = 4096 + 10, len = 21, inf = 1e18;
const ll mod = 1e9 + 7;
pll a[N];
ll b[N], pos[N]; 
int main(){
  	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	ll n, m, ans = 0;
  	cin >> n >> m;
  	for(ll i = 1; i <= n; i++){
  		cin >> a[i].S >> a[i].F;
  		pos[i] = LLONG_MAX;
  	}
  	sort(a + 1, a + n + 1);
  	for(ll i = 1; i <= m; i++){
  		cin >> b[i];
  	}
  	sort(b + 1, b + 1 + m);
  	for(ll i = 1; i <= n; i++){
  		ll from = -1;
  		//cout << a[i].F << " "<< a[i].S << endl;
  		for(ll j = 1; j <= m; j++){
  			if(b[j] >= a[i].S){
  				from = j;
  				break;
  			}
  		}
  		if(from != -1){
	  		for(ll j = n - 1; j >= 0; j--){
	  			if(pos[j] == LLONG_MAX) continue;
	  			if(pos[j] < from) pos[j + 1] = min(pos[j + 1], from);
	  			else{
	  				if(pos[j] < m) pos[j + 1] = min(pos[j + 1], pos[j] + 1);
	  			}
	  		}
	  		// cout << i << " "<< from << endl;
	  		// for(ll j = 1; j <= n; j++){
	  			// cout << pos[j] << " ";
	  		// }
	  		// cout << endl;
  		}
  	}
  	for(ll i = 1; i <= n; i++){
  		if(pos[i] != LLONG_MAX) ans = i;
  	}
  	cout << ans;
  return 0;
}

 

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