Submission #110385

#TimeUsernameProblemLanguageResultExecution timeMemory
110385sofhiasouzaExhibition (JOI19_ho_t2)C++14
50 / 100
106 ms8464 KiB
#include <bits/stdc++.h>
#define MAXN 1010
#define mp make_pair
using namespace std;
typedef pair < int, int > ii;

int n, m, c[MAXN], dp[MAXN][MAXN];
ii phot[MAXN];

inline int func(int u, int ini)
{
	if(u >= n or ini >= m) return 0;
	if(dp[u][ini] != -1) return dp[u][ini];

	int naop = func(u+1, ini);
	int pega;
	int i = ini, f = m-1, r = -1;
	while(i <= f)
	{
		int meio = (i+f)/2;
		if(c[meio] >= phot[u].second)
		{
			r = meio;
			f = meio - 1;
		}
		else i = meio+1;
	} 
	if(r == -1) pega = 0;
	else pega = func(u+1, r+1) + 1;
	return dp[u][ini] = max(pega, naop); 
}

int main()
{
	cin >> n >> m;
	memset(dp, -1, sizeof dp);
	for(int i = 0 ; i < n ; i++)
	{
		cin >> phot[i].second >> phot[i].first;
	}
	for(int i = 0 ; i < m ; i++)
	{
		cin >> c[i];
	}
	sort(c, c+m);
	sort(phot, phot+n);
	int r = func(0, 0);
	cout << r << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...