#include<bits/stdc++.h> using namespace std; int n, c; pair<int, int> x[1000005]; long long dp[1000005][2], wart[1000005], wart2[1000005]; vector<int> v; int main() { cin >> n >> c; for(int i = 1; i <= n; i++) cin >> x[i].first >> x[i].second; sort(x + 1, x + 1 + n); int last = n + 1; for(int i = n; i > 0; i--) //zamiast i + 1 dajemy indeks ostatniego chlopa ktory ma inny wie niz my + zmienic cos w wart[typ[i]] bo to moze trzymac wartosc typu ktory ustawil gosc o tej samej wielkosci co my { dp[i][0] = max(dp[i + 1][0], dp[i + 1][1]); dp[i][1] = max(dp[last][0] - c, max(dp[last][1] - c, wart[x[i].second])) + x[i].first; wart2[x[i].second] = max(wart2[x[i].second], dp[i][1]); v.push_back(x[i].second); if(x[i].first != x[i - 1].first) { last = i; for(auto el : v) { wart[el] = max(wart[el], wart2[el]); wart2[el] = 0; } v.clear(); } } cout << max(dp[1][0], dp[1][1]); } /* 3 5 1 1 3 2 4 3 */
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 | #include<bits/stdc++.h> using namespace std; int n, c; pair<int, int> x[1000005]; long long dp[1000005][2], wart[1000005], wart2[1000005]; vector<int> v; int main() { cin >> n >> c; for(int i = 1; i <= n; i++) cin >> x[i].first >> x[i].second; sort(x + 1, x + 1 + n); int last = n + 1; for(int i = n; i > 0; i--) //zamiast i + 1 dajemy indeks ostatniego chlopa ktory ma inny wie niz my + zmienic cos w wart[typ[i]] bo to moze trzymac wartosc typu ktory ustawil gosc o tej samej wielkosci co my { dp[i][0] = max(dp[i + 1][0], dp[i + 1][1]); dp[i][1] = max(dp[last][0] - c, max(dp[last][1] - c, wart[x[i].second])) + x[i].first; wart2[x[i].second] = max(wart2[x[i].second], dp[i][1]); v.push_back(x[i].second); if(x[i].first != x[i - 1].first) { last = i; for(auto el : v) { wart[el] = max(wart[el], wart2[el]); wart2[el] = 0; } v.clear(); } } cout << max(dp[1][0], dp[1][1]); } /* 3 5 1 1 3 2 4 3 */ |