class Solution {
public:
    using pii = pair<int, int>;
   

    int constrainedSubsetSum(vector<int>& nums, int k) {
        // Let dp[i] be the solution for the prefix of the array that ends at index i,
        //     if the element at index i is in the subsequence.
        // dp[i] = nums[i] + max(0, dp[i-k], dp[i-k+1], ..., dp[i-1])

        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        int curRes = dp[0];
        
        // <idx, value>
        auto cmp = [](const pii& a, const pii& b) {
            return a.second < b.second;
        };
        priority_queue<pii, vector<pii>, decltype(cmp)> maxHeap(cmp);
         
        maxHeap.push({0, dp[0]});

        auto findInWindow = [](int minIdx, decltype(maxHeap)& window) {
            bool foundInWin = false;
            while(!window.empty()) {
                auto node = window.top();
                if(minIdx <= node.first) {
                    // window.pop();
                    return max(0, node.second);
                } else {
                    window.pop();
                }
            }
            return 0;
        };

        for(int i = 1; i < n; ++i) {
            dp[i] = nums[i] + findInWindow(max(0, i - k), maxHeap);
            curRes = max(curRes, dp[i]);
            // cout << i << "->    " << dp[i] << endl;
            maxHeap.push({i, dp[i]});
        }
        return curRes;
    }
}

class Solution {
public:
    
    using pii = pair<int, int>;
 
    static constexpr auto cmp = [](const pii& a, const pii& b) {
        return a.second < b.second;
    };

    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        // first: yi + yj + |xi - xj| == yj + xj + yi - xi
        // so: for each j, we shall found the biggest yi - xi and |xj - xi| <= k
        // using a priority_queue to store those yi - xi
        
        int n = points.size();
        // priority_queue<pii, vector<pii>, decltype(cmp)> maxHeapOri(cmp);
        priority_queue<pii, vector<pii>, decltype(cmp)> maxHeap(cmp);
        maxHeap.push({points[0][0], points[0][1] - points[0][0]}); // init it

        int curRes = INT_MIN;
        for(int j = 1; j < n; ++j) {
            // |xj - xi| <= k, we should consider xj - xi <= k or xi - xj <= k
            // but we can only consider those xj > xi, cause, when we try to consider xj < xi, 
            // the bigger J after j will be like xi, so all cases coverd
            int xj = points[j][0];
            int yj = points[j][1];
            // cout << "dealing: " << xj << " " << yj << endl;
            // auto maxHeap = maxHeapOri;
            while(1) {
                if(maxHeap.empty()) {
                    break;
                }

                auto t = maxHeap.top();
                int xi = t.first;
                int delatI = t.second;
                if(xi != xj ) {
                    if(xj - xi > k) {
                        // cout << "pop: " << xi << endl;
                        maxHeap.pop();
                    } else {
                        curRes = max(curRes, yj + xj + delatI);
                        break;
                    }    
                } else {
                    break;
                }
            }
            maxHeap.push({points[j][0], points[j][1] - points[j][0]});
        }
        return curRes;
        
    }
}

class Solution {
public:
    #define PI 3.14159265
 
    using Point = pair<pair<int, int>, double>;
    
    int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {

        vector<Point> calPoints;
        int n = points.size();
        int dupWithOriCnt = 0;
        // start form the negx: from -179.999 to 180
        auto calDegreeForPoints = [&](vector<int>& xy, vector<Point>& calPoints) {
            int x = xy[0] - location[0];
            int y = xy[1] - location[1];
            if(0 == x && 0 == y) {
                dupWithOriCnt += 1;
                return;
            }
            double result;
            result = atan2 (y, x) * 180 / PI;
            calPoints.emplace_back(Point{{x, y}, result});
        };   

        for(auto& p : points) {
            calDegreeForPoints(p, calPoints);
        }

        // all duplicated
        if(0 == calPoints.size()) {
            return dupWithOriCnt;
        }

        // sort by the angle
        sort(calPoints.begin(), calPoints.end(), [](const Point& a, const Point& b) {
            return a.second < b.second;
        });
        for(int i = 0; i < n; ++i) { // solve the circle problem
            auto p = calPoints[i];
            p.second += 360.0;
            calPoints.push_back(p);
        }

        // init window
        int st = 0;
        int ed = 0;

        double dAngle = angle;

        while(ed < calPoints.size() && calPoints[ed].second - calPoints[st].second <= dAngle) {
            ++ed;
        }
        --ed;
        int finRes = ed - st + 1;

        // mv window
        while(ed < calPoints.size()) {
            // mv st
            ++st;
            while(ed < calPoints.size() && calPoints[ed].second - calPoints[st].second <= dAngle) {
                ++ed;
            }
            if(ed == calPoints.size()) {
                finRes = max(finRes, static_cast<int>(calPoints.size()) - st);
            } else {
                --ed;
                finRes = max(finRes, ed - st + 1);
            }

        }

        return finRes + dupWithOriCnt;
    }
}

class Solution {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        // alway keep st,ed as the max status:
        // score(st, ed) <= k, ed cannot be bigger for each st
        // then we statistic for each st, how many ways start with st

        // moving window score = getScore(nums[st:ed])
        long long st = 0; 
        long long ed = 0;
        long long n = nums.size();
        long long curScore = 0;
        long long cnt = 0;
        while(st < n) {
            bool edMoved = false;
            while(ed < n && (curScore + nums[ed])*(ed - st + 1) < k) {
                curScore += nums[ed];
                ++ed;
                edMoved = true;
            }

            // add cnt start with cur st
            if(curScore*(ed - st) < k) {
                cnt += ed - st;
            }
            
            curScore -= nums[st];
            ++st;
        }
        return cnt;
    }
};