Submission

Score: 100

User: Peerawat

Problemset: ความลึก

Language: cpp

Time: 0.197 second

Submitted On: 2026-10-06 15:39:17

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,q;
    cin >> n >> q;

    vector<int> sh;
    vector<int> sw;
    vector<int> most(n+2,0);

    int h=0;
    for(int i=0;i<=n;i++){
        long long x=0;
        if (i<n){
            int d;
            cin >> d >> x;
            h += d;
        }
        else{
            h = 0;
        }

        long long sum = 0;

        while(!sh.empty() && sh.back()>=h ){
            if(sh.back() > h && sw.back() + sum > most[sh.back()]){
                most[sh.back()] = sw.back() + sum;
            }
            sum += sw.back();
            sh.pop_back();
            sw.pop_back();
        }

        if(i < n){
            sh.push_back(h);
            sw.push_back(x + sum);
        }

    }

    for(int i = n-1 ; i>= 1;i--){
        if(most[i+1]>most[i]){
            most[i] = most[i+1];
        }
    }

    while(q--){
        long long w;
        cin >> w;
        int lo=0,hi=n,ans=0;
        while(lo <= hi){
            int mid;
            mid = (lo+hi)/2;
            if(most[mid] >= w || mid == 0){
                ans = mid;
                lo = mid+1;
            }
            else{
                hi = mid-1;
            }
        }
        cout << ans << "\n";
    }
}