#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n,c; cin>>n>>c; vector<pair<int, int>> klocki(n, pair<int,int>()); vector<vector<int>> sorted_blocks(500001, vector<int>()); set<int> colors; map<int, int> colorsMapping; for(int i=0; i<n; i++) { cin>>klocki[i].first>>klocki[i].second; colors.insert(klocki[i].second); } int colors_num = colors.size(); int color_idx = 0; for( auto iter = colors.begin(); iter != colors.end(); ++iter, ++color_idx ) { colorsMapping[*iter] = color_idx; } for(int i=0; i<klocki.size(); i++) { klocki[i].second = colorsMapping[klocki[i].second]; } /*for(int i=0; i<klocki.size(); i++) { cout << klocki[i].first << " " << klocki[i].second << endl; } */ //sort(klocki.begin(), klocki.end()); for(int i=0; i<n; i++) { sorted_blocks[klocki[i].first].push_back(klocki[i].second); } //vector<vector<long long>> results(colors_num, vector<long long> (klocki.back().first+1)); vector<long long> results(colors_num, 0); // w 1 iteracji mamy bloczki 1 to po prostu bierzemy maxa z nich // 2 iteracja: w sumie trzeba wiedziec jaki kolor byl poprzednio, to wtedy bedziemy trzymac liczba kolorow wynikow ktore koncza sie na i-tym kolorze // czyli dokladajac klocek o danym kolorze i size musimy wiedziec czy zgadzaja nam sie kolory zeby wyliczyc nowa wartosc - do tego potrzebna poprzednia stara wartosc results // i jeszcze maksymalna wartosc results ale dla danego size... std::map<int, long long> results_changes; long long value; long long max_results=0; int color, penalty=c; for(int waga=1; waga<=klocki.back().first; waga++) { results_changes.clear(); for(int i=0; i<sorted_blocks[waga].size(); i++) { color = sorted_blocks[waga][i]; value = max(results[color] + waga, max_results + waga - penalty);// wziac albo results dla tego samego koloru i dodac te wartosci albo max z results... poprzedniego results_changes[sorted_blocks[waga][i]] = value; } for( auto iter = results_changes.begin(); iter != results_changes.end(); ++iter) { //cout << (*iter).first << " " << (*iter).second << endl; results[(*iter).first] = (*iter).second; max_results = max(max_results, (*iter).second); } } /*for(int i=0; i<results.size(); i++) { cout << results[i] << " "; } cout << endl;*/ cout << *std::max_element(results.begin(), results.end()) << endl; 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 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n,c; cin>>n>>c; vector<pair<int, int>> klocki(n, pair<int,int>()); vector<vector<int>> sorted_blocks(500001, vector<int>()); set<int> colors; map<int, int> colorsMapping; for(int i=0; i<n; i++) { cin>>klocki[i].first>>klocki[i].second; colors.insert(klocki[i].second); } int colors_num = colors.size(); int color_idx = 0; for( auto iter = colors.begin(); iter != colors.end(); ++iter, ++color_idx ) { colorsMapping[*iter] = color_idx; } for(int i=0; i<klocki.size(); i++) { klocki[i].second = colorsMapping[klocki[i].second]; } /*for(int i=0; i<klocki.size(); i++) { cout << klocki[i].first << " " << klocki[i].second << endl; } */ //sort(klocki.begin(), klocki.end()); for(int i=0; i<n; i++) { sorted_blocks[klocki[i].first].push_back(klocki[i].second); } //vector<vector<long long>> results(colors_num, vector<long long> (klocki.back().first+1)); vector<long long> results(colors_num, 0); // w 1 iteracji mamy bloczki 1 to po prostu bierzemy maxa z nich // 2 iteracja: w sumie trzeba wiedziec jaki kolor byl poprzednio, to wtedy bedziemy trzymac liczba kolorow wynikow ktore koncza sie na i-tym kolorze // czyli dokladajac klocek o danym kolorze i size musimy wiedziec czy zgadzaja nam sie kolory zeby wyliczyc nowa wartosc - do tego potrzebna poprzednia stara wartosc results // i jeszcze maksymalna wartosc results ale dla danego size... std::map<int, long long> results_changes; long long value; long long max_results=0; int color, penalty=c; for(int waga=1; waga<=klocki.back().first; waga++) { results_changes.clear(); for(int i=0; i<sorted_blocks[waga].size(); i++) { color = sorted_blocks[waga][i]; value = max(results[color] + waga, max_results + waga - penalty);// wziac albo results dla tego samego koloru i dodac te wartosci albo max z results... poprzedniego results_changes[sorted_blocks[waga][i]] = value; } for( auto iter = results_changes.begin(); iter != results_changes.end(); ++iter) { //cout << (*iter).first << " " << (*iter).second << endl; results[(*iter).first] = (*iter).second; max_results = max(max_results, (*iter).second); } } /*for(int i=0; i<results.size(); i++) { cout << results[i] << " "; } cout << endl;*/ cout << *std::max_element(results.begin(), results.end()) << endl; return 0; } |