zoj 3187 Inviting Friends

zoj 3187 Inviting Friends

#include<iostream>#include<cstdio>#include<cmath>#include<string.h>using namespace std;const int MAXN=110;const long long INF=100100000LL;bool flag;long long n,m,i,mid,now,l,r,had[MAXN],per[MAXN],s1[MAXN],p1[MAXN],p2[MAXN],s2[MAXN],need,cost,a,b;int main(){scanf("%lld%lld",&n,&m);while (n!=0&&m!=0){for (i=1;i<=n;i++)scanf("%lld%lld%lld%lld%lld%lld",&per[i],&had[i],&s1[i],&p1[i],&s2[i],&p2[i]);l=0; r=INF;while (l<r){mid=(l+r)>>1; mid++;now=m; flag=true;for (i=1;i<=n;i++){need=per[i]*mid-had[i];cost=INF;for (b=0;b<=s1[i]+1;b++){if (s2[i]*b>=need) a=0;else a=(need-s2[i]*b+s1[i]-1)/s1[i];cost=min(cost,b*p2[i]+a*p1[i]);}for (a=0;a<=s2[i]+1;a++){if (s1[i]*a>=need) b=0;else b=(need-s1[i]*a+s2[i]-1)/s2[i];cost=min(cost,b*p2[i]+a*p1[i]);}now-=cost;if (now<0){flag=false; break;}}if (flag) l=mid;else r=mid-1;}printf("%lldn",l);scanf("%lld%lld",&n,&m);}return 0;}