oj.uz

Submission #147233

# Submission time Handle Problem Language Result Execution time Memory
147233 2019-08-28T13:00:23 Z joulej Exhibition (JOI19_ho_t2) C++17
0 / 100
 2 ms 376 KB 
#include <iostream>
#include <algorithm>
#include <vector>

using std::cin;
using std::cout;
using std::sort;
using std::lower_bound;
using std::pair;

void fast_io()
{
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}

const int MAX_N = (int)1e5 + 777;
const int INF = (int)2e9;

int n, m;
pair<int, int> pictures[MAX_N];
int frames[MAX_N];

int a[MAX_N], dp[MAX_N];

void solve()
{
	cin >> n >> m;

	for(int i = 0; i < n; ++i)
		cin >> pictures[i].second >> pictures[i].first;

	for(int j = 0; j < m; ++j)
		cin >> frames[j];

	sort(pictures, pictures + n);
	sort(frames, frames + m);

	for(int i = 0; i < n; ++i)
		a[i] = lower_bound(frames, frames + m, pictures[i].second) - frames;

#ifdef __LOCAL
	cout << "a: ";

	for(int i = 0; i < n; ++i)
		cout << a[i] << " ";

	cout << "\n";
#endif

	for(int len = 1; len <= n; ++len)
		dp[len] = INF;

	dp[0] = -INF;

	for(int i = 0; i < n; ++i)
	{
		for(int len = n - 1; len >= 0; --len)
		{
			int val = (dp[len] + 1 >= a[i] ? dp[len] + 1 : a[i]);

			if(val < m)
				dp[len + 1] = (val < dp[len + 1] ? val : dp[len + 1]);
		}
	}

#ifdef __LOCAL
	cout << "dp: ";

	for(int len = 0; len <= n; ++len)
		cout << dp[len] << " ";

	cout << "\n";
#endif

	int answ = 0;

	while(dp[answ + 1] < m)
		++answ;

	cout << answ << "\n";
}

int main()
{
	fast_io();
	solve();

	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -