实战演练：$vjudge$联赛专题训练第一弹——做题记录分享
最编程
2024-08-07 18:58:16
...
//#include<bits/stdc++.h>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<cstdio>
using namespace std;
#define il inline
#define int long long
#define gc getchar()
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
const int N=30,inf=1e18;
int n,C,as,cnt,use[N];
bool gdgs=1;
struct node{int val,num;}nod[N];
il int read()
{
rc ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il bool cmp(node gd,node gs){return gd.val<gs.val;}
il void cal()
{
while(gdgs)
{
memset(use,0,sizeof(use));rb flg=0;ri tmp_c=C;
my(i,cnt,1)
{ri lim=min(tmp_c/nod[i].val,nod[i].num);tmp_c-=lim*nod[i].val;use[i]=lim;if(!tmp_c){flg=1;i=0;}}
if(tmp_c>0)
rp(i,1,cnt)
{
if(nod[i].num>use[i])
while(nod[i].num>use[i]){tmp_c-=nod[i].val;++use[i];if(tmp_c<0){flg=1;break;}}
if(flg)i=cnt+10;
}
if(!flg)return;
ri tmp=inf;rp(i,1,cnt)if(use[i])tmp=min(tmp,nod[i].num/use[i]);
as+=tmp;rp(i,1,cnt)nod[i].num-=use[i]*tmp;
}
}
signed main()
{
//freopen("A.in","r",stdin);freopen("A.out","w",stdout);
n=read();C=read();rp(i,1,n){ri v=read(),b=read();if(v>C){as+=b;continue;}nod[++cnt]=(node){v,b};}
sort(nod+1,nod+1+cnt,cmp);cal();printf("%lld\n",as);
return 0;
}