Codeforces/mysterious_optimized.cpp at master · suraj95/Codeforces · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/*

Chain here is such a sequence of envelopes A = {a1,  a2,  ...,  an}, where the width and
the height of the i-th envelope is strictly higher than the width and the height of the
(i  -  1)th envelope respectively. Chain size is the number of envelopes in the chain.

We have to make the chain of the maximum size from the envelopes, such that we will be able
to put a card into it. The card fits into the chain if its width and height is lower than the
width and the height of the smallest envelope in the chain respectively.

author: https://github.com/Waqar-107

*/

#define _CRT_SECURE_NO_WARNINGS

#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<functional>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<utility>
#include<vector>

#define N 5010

using namespace std;

struct env
{
	int w, h, idx;
	env() {}
	env(int w, int h, int idx) {
		this->w = w;
		this->h = h;
		this->idx = idx;
	}
};

bool cmp(env a, env b) {
	if (a.w == b.w)
		return a.h < b.h;

	return a.w < b.w;
}

int w, h;
vector<env> vec;
int dp[N];
int parent[N];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  	int i, j, k;
	int n, m;

 	scanf("%d %d %d",&n,&w,&h);

	for (i = 1; i <= n; i++)
	{

		scanf("%d %d",&j,&k);

		if (j > w && k > h)
			vec.push_back(env(j, k, i));
	}

	if (vec.size() == 0) {

		printf("0\n");
		return 0;
	}

	sort(vec.begin(), vec.end(), cmp);

	n = vec.size();

	memset(dp, 0, sizeof(dp));
	memset(parent, -1, sizeof(parent));

	dp[0] = 1;
	for (i = 1; i < n; i++)
	{
		for (j = i - 1; j >= 0; j--)
		{
			if (vec[j].w < vec[i].w && vec[j].h < vec[i].h)
			{
				if (1 + dp[j] > dp[i])
				{
					dp[i] = 1 + dp[j];
					parent[i] = j;
				}
			}
		}

		if (!dp[i])dp[i] = 1;
	}

	int mx = 1; k = 0;
	for (i = 1; i < n; i++)
	{
		if (dp[i] > mx)
			mx = dp[i], k = i;
	}


	// endl forces us to empty the buffer stream which is unnecessary

	printf("%d\n",mx);

	vector<int> ans; ans.push_back(vec[k].idx);
	while (1)
	{
		k = parent[k];
		if (k == -1)break;

		ans.push_back(vec[k].idx);
	}

	reverse(ans.begin(), ans.end());
	for (int e : ans)

		printf("%d\n",e);

	return 0;
}