Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- typedef std::pair<std::pair<int, int> , int> para;
- bool comp(para p1, para p2)
- {
- if(p1.first.first != p2.first.first)
- return p1.first.first < p2.first.first;
- else
- return p1.first.second < p2.first.second;
- }
- int main()
- {
- std::vector<para> tab;
- std::pair<int, int> w;
- for(int i = 1; scanf("%d %d", &w.first, &w.second) != EOF; ++i)
- {
- tab.push_back(std::make_pair(w, i));
- }
- std::sort(tab.begin(), tab.end(), comp);
- int *poprzednik = new int[tab.size()+1];
- int *d = new int[tab.size()+1];
- d[0] = 1;
- poprzednik[0] = -1;
- for(int i = 1; i < tab.size(); ++i)
- {
- int act = tab[i].first.second;
- d[i] = 1;
- poprzednik[i] = -1;
- for(int j = 0; j < i; ++j)
- {
- if(act < tab[j].first.second)
- {
- if(d[i] <= d[j])
- {
- d[i] = d[j]+1;
- poprzednik[i] = j;
- }
- }
- }
- }
- int MAX = 0;
- int poprzmax;
- for(int i = 0; i < tab.size(); ++i)
- {
- if(d[i] > MAX)
- {
- MAX = d[i];
- poprzmax = i;
- }
- }
- printf("%d\n", MAX);
- while(poprzmax != -1)
- {
- printf("%d\n", tab[poprzmax].second);
- poprzmax = poprzednik[poprzmax];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement