Untitled

 avatar
unknown
c_cpp
a month ago
1.2 kB
4
Indexable
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