[HOJ] 203 - 書架

#include<stdio.h>
#include<set>
using namespace std;
multiset<long long int> bst;
#define N 100005
int h[N],w[N],s[N];
long long int dp[N],sum=0;
int main(){
    int n,m,i,j,l=1,r=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d%d",&h[i],&w[i]);
        for(s[++r]=i-1;l<r && h[s[r]]<=h[i];r--)
            bst.erase(bst.find(dp[s[r-1]]+h[s[r]]));
        bst.insert(dp[s[r]]+h[i]);
        s[r+1]=i;
        for(sum+=w[i];sum>m;sum-=w[s[l]]){
            bst.erase(bst.find(dp[s[l]]+h[s[l+1]]));
            if(++s[l]==s[l+1]) l++;
            else bst.insert(dp[s[l]]+h[s[l+1]]);
        }
        dp[i]=*bst.begin();
    }
    printf("%lld\n",dp[n]);
}