#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; #define ll long long #define ull unsigned ll #define pb push_back #define pii pair<int,int> #define pl pair<ll,ll> #define F first #define S second #define pq priority_queue #define all(x) x.begin(), x.end() #define deb(x) cout << #x << " = " << x << '\n'; #define deb2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << '\n'; constexpr int M = 1e9+7; constexpr int N = 5e5+7; constexpr bool debug = 0; map<pii,int> was; ll dp[N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, c; cin >> n >> c; ll cmax = 0, maxo = 0, lasta1 = 0; for(int i = 0; i < n; i++){ ll a1, w1; cin >> a1 >> w1; if(was[{a1, w1}] == 1) continue; was[{a1, w1}] = 1; if(lasta1 != a1){ maxo = cmax; lasta1 = a1; } dp[w1] = max(dp[w1], maxo-c)+a1; cmax = max(cmax,dp[w1]); //deb2(maxo, cmax); } maxo = cmax; cout << maxo; 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 | #include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; #define ll long long #define ull unsigned ll #define pb push_back #define pii pair<int,int> #define pl pair<ll,ll> #define F first #define S second #define pq priority_queue #define all(x) x.begin(), x.end() #define deb(x) cout << #x << " = " << x << '\n'; #define deb2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << '\n'; constexpr int M = 1e9+7; constexpr int N = 5e5+7; constexpr bool debug = 0; map<pii,int> was; ll dp[N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, c; cin >> n >> c; ll cmax = 0, maxo = 0, lasta1 = 0; for(int i = 0; i < n; i++){ ll a1, w1; cin >> a1 >> w1; if(was[{a1, w1}] == 1) continue; was[{a1, w1}] = 1; if(lasta1 != a1){ maxo = cmax; lasta1 = a1; } dp[w1] = max(dp[w1], maxo-c)+a1; cmax = max(cmax,dp[w1]); //deb2(maxo, cmax); } maxo = cmax; cout << maxo; return 0; } |