#ifndef LOCAL #pragma GCC optimize("O3,unroll-loops") #endif #include <bits/stdc++.h> #define fi first #define se second #define pn printf("\n") #define ssize(x) int(x.size()) #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define bitcount(x) __builtin_popcount(x) #define clz(x) __builtin_clz(x) #define ctz(x) __builtin_ctz(x) #define mp make_pair //~ #define r(x) resize(x) //~ #define rf(x, c) resize(x, c) using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<int, ll> pil; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef double db; typedef long double ldb; #define V vector int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1; int add(int a, int b){return a+b >= mod ? a+b - mod : a+b;} int sub(int a, int b){return a-b < 0 ? a-b + mod : a-b;} int mul(int a, int b){return int(a * ll(b) % mod);} int fpow(int a, ll b){ int ret = 1; while(b){ if(b & 1) ret = mul(ret, a); b >>= 1, a = mul(a, a); } return ret; } int inv(int a){ return fpow(a, mod-2); } struct coeff{ V<int> fac, invfac; coeff(int n){ fac.resize(n+1), invfac.resize(n+1); fac[0] = 1, invfac[0] = 1; for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i-1], i); invfac[n] = inv(fac[n]); for(int i = n-1; i; --i) invfac[i] = mul(invfac[i+1], i+1); } int get(int n, int k){ if(n < k) return 0; return mul(fac[n], mul(invfac[n-k], invfac[k])); } }; void answer(){ int n; ll c; scanf("%d%lld", &n, &c); V<set<int>> t(500001); for(int i = 0, a, b; i < n; ++i) scanf("%d%d", &a, &b), t[a].emplace(b); V<ll> dp(500001, 0); ll best_dp = 0; for(int i = 500000; i >= 1; --i){ ll new_best = 0; for(int u : t[i]){ dp[u] = max(dp[u]+i, best_dp+i-c); new_best = max(new_best, dp[u]); } best_dp = max(best_dp, new_best); } printf("%lld\n", best_dp); } int main(){ int T = 1; // scanf("%d", &T); //~ ios_base::sync_with_stdio(0); cin.tie(0); cin >> T; for(++T; --T; ) answer(); 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 | #ifndef LOCAL #pragma GCC optimize("O3,unroll-loops") #endif #include <bits/stdc++.h> #define fi first #define se second #define pn printf("\n") #define ssize(x) int(x.size()) #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define bitcount(x) __builtin_popcount(x) #define clz(x) __builtin_clz(x) #define ctz(x) __builtin_ctz(x) #define mp make_pair //~ #define r(x) resize(x) //~ #define rf(x, c) resize(x, c) using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<int, ll> pil; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef double db; typedef long double ldb; #define V vector int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1; int add(int a, int b){return a+b >= mod ? a+b - mod : a+b;} int sub(int a, int b){return a-b < 0 ? a-b + mod : a-b;} int mul(int a, int b){return int(a * ll(b) % mod);} int fpow(int a, ll b){ int ret = 1; while(b){ if(b & 1) ret = mul(ret, a); b >>= 1, a = mul(a, a); } return ret; } int inv(int a){ return fpow(a, mod-2); } struct coeff{ V<int> fac, invfac; coeff(int n){ fac.resize(n+1), invfac.resize(n+1); fac[0] = 1, invfac[0] = 1; for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i-1], i); invfac[n] = inv(fac[n]); for(int i = n-1; i; --i) invfac[i] = mul(invfac[i+1], i+1); } int get(int n, int k){ if(n < k) return 0; return mul(fac[n], mul(invfac[n-k], invfac[k])); } }; void answer(){ int n; ll c; scanf("%d%lld", &n, &c); V<set<int>> t(500001); for(int i = 0, a, b; i < n; ++i) scanf("%d%d", &a, &b), t[a].emplace(b); V<ll> dp(500001, 0); ll best_dp = 0; for(int i = 500000; i >= 1; --i){ ll new_best = 0; for(int u : t[i]){ dp[u] = max(dp[u]+i, best_dp+i-c); new_best = max(new_best, dp[u]); } best_dp = max(best_dp, new_best); } printf("%lld\n", best_dp); } int main(){ int T = 1; // scanf("%d", &T); //~ ios_base::sync_with_stdio(0); cin.tie(0); cin >> T; for(++T; --T; ) answer(); return 0; } |