记录编号	313627	评测结果	AAAAAAAAAA
题目名称	采药(加强版)	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.681 s
提交时间	2016-10-01 17:51:51	内存使用	0.75 MiB

#include<cstdio>
const int maxn=40005;
int c[25][25];//c[volume][value]
struct queue{
    int q[maxn],ind[maxn];
    int lim,w,head,tail;
    void clear(int _lim,int _w){
        lim=_lim;w=_w;head=tail=0;
    }
    void add(int x,int i){
        while(head!=tail&&i-ind[head]>lim)head++;
        while(head!=tail&&q[tail-1]+(i-ind[tail-1])*w<=x)tail--;
        q[tail]=x;ind[tail++]=i;
    }
    int qmax(){
        return q[head];
    }
    int qpos(){
        return ind[head];
    }
}q1;
int f[maxn];
int main(){
    freopen("crazytime.in","r",stdin);
    freopen("crazytime.out","w",stdout);
    int n,m;scanf("%d %d",&n,&m);
    int a,b;
    while(n--){
        scanf("%d%d",&a,&b);
        c[a][b]++;
    }
    for(int i=1;i<=20;++i){//volume
        for(int j=1;j<=20;++j){//value
            if(!c[i][j])continue;
           
            for(int r=0;r<i;++r){
                 q1.clear(c[i][j],j);
                for(int k=0;k*i+r<=m;++k){
                    q1.add(f[k*i+r],k);
                    f[k*i+r]=q1.qmax()+j*(k-q1.qpos());
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=m;++i){
        if(f[i]>ans){
            ans=f[i];
        }
    }
    printf("%d\n",ans);
    fclose(stdin);fclose(stdout);
    return 0;
}