oj.uz

Submission #147235

# Submission time Handle Problem Language Result Execution time Memory
147235 2019-08-28T13:07:45 Z joulej Exhibition (JOI19_ho_t2) C++17
50 / 100
 1000 ms 5204 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 + 27; ++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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 380 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 380 KB Output is correct
20 Correct 4 ms 376 KB Output is correct
21 Correct 4 ms 376 KB Output is correct
22 Correct 4 ms 376 KB Output is correct
23 Correct 4 ms 380 KB Output is correct
24 Correct 4 ms 376 KB Output is correct
25 Correct 6 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 4 ms 376 KB Output is correct
28 Correct 4 ms 376 KB Output is correct
29 Correct 4 ms 376 KB Output is correct
30 Correct 4 ms 376 KB Output is correct
31 Correct 4 ms 376 KB Output is correct
32 Correct 4 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 4 ms 376 KB Output is correct
35 Correct 3 ms 376 KB Output is correct
36 Correct 4 ms 380 KB Output is correct
37 Correct 4 ms 376 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 380 KB Output is correct
20 Correct 4 ms 376 KB Output is correct
21 Correct 4 ms 376 KB Output is correct
22 Correct 4 ms 376 KB Output is correct
23 Correct 4 ms 380 KB Output is correct
24 Correct 4 ms 376 KB Output is correct
25 Correct 6 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 4 ms 376 KB Output is correct
28 Correct 4 ms 376 KB Output is correct
29 Correct 4 ms 376 KB Output is correct
30 Correct 4 ms 376 KB Output is correct
31 Correct 4 ms 376 KB Output is correct
32 Correct 4 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 4 ms 376 KB Output is correct
35 Correct 3 ms 376 KB Output is correct
36 Correct 4 ms 380 KB Output is correct
37 Correct 4 ms 376 KB Output is correct
38 Execution timed out 1072 ms 5204 KB Time limit exceeded
39 Halted 0 ms 0 KB -