Submission #110385

#	Time	Username	Problem	Language	Result	Execution time	Memory
110385		sofhiasouza	Exhibition (JOI19_ho_t2)	C++14	50 / 100	106 ms	8464 KiB

joi2019_ho_t2

#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;
}

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