Submission #97404

#TimeUsernameProblemLanguageResultExecution timeMemory
97404MatheusLealVExhibition (JOI19_ho_t2)C++17
50 / 100
28 ms17792 KiB
#include <bits/stdc++.h>
#define N 1050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

pii p[N];

ll n, m, dp[N][N], c[N];

ll solve(int i, int j)
{
	if(i > n or j > m) return 0;

	if(dp[i][j] != -1) return dp[i][j];

	int A = 0, B = solve(i + 1, j), C = solve(i, j + 1);

	if(p[i].s <= c[j]) A = solve(i + 1, j + 1) + 1;

	return dp[i][j] = max({A, B, C});
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>m;

	memset(dp, -1, sizeof dp);

	for(int i = 1; i <= n; i++) cin>>p[i].s>>p[i].f;

	for(int i = 1; i <= m; i++) cin>>c[i];

	sort(c + 1, c + m + 1);

	sort(p + 1, p + n + 1);

	cout<<solve(1, 1)<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...