Untitled
using ll = long long; class Solution { public: long long maximumCoins(vector<vector<int>>& a, int k) { sort(a.begin(), a.end()); int l = 0, r = 0, n = a.size(); ll res = 0, t = 0; while(r < n) { t += (ll)a[r][2] * (a[r][1] - a[r][0] + 1); ll s = a[r][1] - k + 1; while(l < r && a[l][1] < s) { t -= (ll)a[l][2] * (a[l][1] - a[l][0] + 1); l++; } if(s > a[l][0]) { res = max(res, t - (s - a[l][0]) * a[l][2]); } else { res = max(res, t); } r++; } // cout << 1; t = 0, r = 0, l = 0; while(l < n) { ll s = a[l][0] + k - 1; while(r < n && a[r][0] <= s) { t += (ll)a[r][2] * (a[r][1] - a[r][0] + 1); r++; } // cout << l << " " << r << endl; if(s < a[r - 1][1]) { res = max(res, t - (a[r - 1][1] - s) * a[r - 1][2]); } else { res = max(res, t); } t -= (ll)a[l][2] * (a[l][1] - a[l][0] + 1); l++; } return res; } };
Leave a Comment