Submission #97404

#	Time	Username	Problem	Language	Result	Execution time	Memory
97404		MatheusLealV	Exhibition (JOI19_ho_t2)	C++17	50 / 100	28 ms	17792 KiB

joi2019_ho_t2

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

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