#include <iostream> #include <vector> #include <cstdlib> #include <algorithm> #include <iomanip> #include <cassert> #include <map> #include <set> void applyNewPunkty(std::map<int, unsigned long long>& noweKolorToPunktyMap, std::map<int, unsigned long long>& kolorToPunktyMap, std::map<unsigned long long, std::set<int>>& punktytoKolorsMap) { for (auto const& [kolor, nowePunkty] : noweKolorToPunktyMap) { unsigned long long starePunkty = kolorToPunktyMap[kolor]; if (punktytoKolorsMap.contains(starePunkty) && punktytoKolorsMap[starePunkty].contains(kolor)) { punktytoKolorsMap[starePunkty].erase(kolor); if (punktytoKolorsMap[starePunkty].size() == 0) punktytoKolorsMap.erase(starePunkty); } punktytoKolorsMap[nowePunkty].insert(kolor); kolorToPunktyMap[kolor] = nowePunkty; } noweKolorToPunktyMap.clear(); } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int n; int kara; std::cin >> n >> kara; std::vector<int> wysokosci; std::vector<int> kolory; for (int i = 0; i < n; ++i) { int wysokosc; int kolor; std::cin >> wysokosc >> kolor; wysokosci.push_back(wysokosc); kolory.push_back(kolor); } std::map<int, unsigned long long> kolorToPunktyMap; std::map<unsigned long long, std::set<int>> punktytoKolorsMap; int ostatniaWysokosc = 0; std::map<int, unsigned long long> noweKolorToPunktyMap; for (int i = 0; i < wysokosci.size(); ++i) { int wysokosc = wysokosci[i]; if (wysokosc > ostatniaWysokosc) { applyNewPunkty(noweKolorToPunktyMap, kolorToPunktyMap, punktytoKolorsMap); ostatniaWysokosc = wysokosc; } unsigned long long maxWynikDlaKoloru = wysokosc; if (kolorToPunktyMap.contains(kolory[i])) maxWynikDlaKoloru = std::max(maxWynikDlaKoloru, kolorToPunktyMap[kolory[i]] + wysokosc); if (punktytoKolorsMap.size() >= 1) { unsigned long long najwiecejPunktow = punktytoKolorsMap.rbegin()->first; if (punktytoKolorsMap[najwiecejPunktow].contains(kolory[i])) maxWynikDlaKoloru = std::max(maxWynikDlaKoloru, najwiecejPunktow + wysokosc); else { if (najwiecejPunktow + wysokosc > kara) maxWynikDlaKoloru = std::max(maxWynikDlaKoloru, najwiecejPunktow + wysokosc - kara); } } noweKolorToPunktyMap[kolory[i]] = maxWynikDlaKoloru; } applyNewPunkty(noweKolorToPunktyMap, kolorToPunktyMap, punktytoKolorsMap); std::cout << punktytoKolorsMap.rbegin()->first; return 0; }
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 | #include <iostream> #include <vector> #include <cstdlib> #include <algorithm> #include <iomanip> #include <cassert> #include <map> #include <set> void applyNewPunkty(std::map<int, unsigned long long>& noweKolorToPunktyMap, std::map<int, unsigned long long>& kolorToPunktyMap, std::map<unsigned long long, std::set<int>>& punktytoKolorsMap) { for (auto const& [kolor, nowePunkty] : noweKolorToPunktyMap) { unsigned long long starePunkty = kolorToPunktyMap[kolor]; if (punktytoKolorsMap.contains(starePunkty) && punktytoKolorsMap[starePunkty].contains(kolor)) { punktytoKolorsMap[starePunkty].erase(kolor); if (punktytoKolorsMap[starePunkty].size() == 0) punktytoKolorsMap.erase(starePunkty); } punktytoKolorsMap[nowePunkty].insert(kolor); kolorToPunktyMap[kolor] = nowePunkty; } noweKolorToPunktyMap.clear(); } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int n; int kara; std::cin >> n >> kara; std::vector<int> wysokosci; std::vector<int> kolory; for (int i = 0; i < n; ++i) { int wysokosc; int kolor; std::cin >> wysokosc >> kolor; wysokosci.push_back(wysokosc); kolory.push_back(kolor); } std::map<int, unsigned long long> kolorToPunktyMap; std::map<unsigned long long, std::set<int>> punktytoKolorsMap; int ostatniaWysokosc = 0; std::map<int, unsigned long long> noweKolorToPunktyMap; for (int i = 0; i < wysokosci.size(); ++i) { int wysokosc = wysokosci[i]; if (wysokosc > ostatniaWysokosc) { applyNewPunkty(noweKolorToPunktyMap, kolorToPunktyMap, punktytoKolorsMap); ostatniaWysokosc = wysokosc; } unsigned long long maxWynikDlaKoloru = wysokosc; if (kolorToPunktyMap.contains(kolory[i])) maxWynikDlaKoloru = std::max(maxWynikDlaKoloru, kolorToPunktyMap[kolory[i]] + wysokosc); if (punktytoKolorsMap.size() >= 1) { unsigned long long najwiecejPunktow = punktytoKolorsMap.rbegin()->first; if (punktytoKolorsMap[najwiecejPunktow].contains(kolory[i])) maxWynikDlaKoloru = std::max(maxWynikDlaKoloru, najwiecejPunktow + wysokosc); else { if (najwiecejPunktow + wysokosc > kara) maxWynikDlaKoloru = std::max(maxWynikDlaKoloru, najwiecejPunktow + wysokosc - kara); } } noweKolorToPunktyMap[kolory[i]] = maxWynikDlaKoloru; } applyNewPunkty(noweKolorToPunktyMap, kolorToPunktyMap, punktytoKolorsMap); std::cout << punktytoKolorsMap.rbegin()->first; return 0; } |