Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <set>
- typedef long long ll;
- struct Pair {
- int x, y;
- };
- int main() {
- freopen("input.txt", "rt", stdin);
- //std::ios_base_sync_with_stdio(false);
- //std::cin.tie(0); std::cout.tie(0); std::cerr.tie(0);
- int n, limit; std::cin >> n >> limit;
- auto cmpx = [](const Pair& a, const Pair& b){
- return a.x < b.x || (a.x == b.x && a.y < b.y);
- };
- auto cmpy = [](const Pair& a, const Pair& b){
- return a.y < b.y || (a.y == b.y && a.x < b.x);
- };
- std::vector<Pair> ordered_x, ordered_y;
- for (int i = 0; i < n; ++i) {
- int x, y; std::cin >> x >> y;
- ordered_x.push_back(Pair{x,y});
- ordered_y.push_back(Pair{x,y});
- }
- std::sort(ordered_x.begin(), ordered_x.end(), cmpx);
- std::sort(ordered_y.begin(), ordered_y.end(), cmpy);
- std::multiset<Pair, decltype(cmpx)> set(cmpx);
- ll answ = 0;
- for (int i = 0; i < n; ++i) {
- while ((int)set.size() < limit && !ordered_x.empty()) {
- auto p = ordered_x.back(); ordered_x.pop_back();
- if (p.y < ordered_y[i].y) continue;
- set.insert(p);
- }
- if ((int)set.size() == limit) {
- for (auto& it : set) {
- std::cout << it.x << ' ' << it.y << std::endl;
- }
- answ = std::max(answ, (ll) set.begin()->x * ordered_y[i].y);
- std::cout << "answ = " << answ << std::endl << std::string(80, '-') << std::endl;
- }
- if (i == 0 || ordered_y[i].y == ordered_y[i-1].y) {
- continue;
- }
- for (int j = i-1; j >= 0 && ordered_y[j].y == ordered_y[i-1].y; --j) {
- if (set.find(ordered_y[j]) != set.end()) {
- set.erase(ordered_y[j]);
- }
- }
- }
- std::cout << answ;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement