Pagini recente » Cod sursa (job #2378346) | Cod sursa (job #2182865) | Cod sursa (job #2789142) | Cod sursa (job #1116922) | Cod sursa (job #901707)
Cod sursa(job #901707)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("garaj.in");
ofstream g("garaj.out");
int i,n,m,c,li,ls,mij,sol,v[100100];
struct cam{int c,t;};
cam a[100100];
int verif(int x)
{
int i;
long long c=0;
for(i=1;i<=n;++i)
{
c+=(x/a[i].t)*a[i].c;
if(c>=m)
return 1;
}
return 0;
}
int main()
{
f>>n>>m;
for(i=1;i<=n;++i)
{
f>>a[i].c>>a[i].t;
a[i].t*=2;
}
li=0;
ls=1<<25;
while(li<=ls)
{
mij=(li+ls)>>1;
if(verif(mij))
ls=mij-1,sol=mij;
else
li=mij+1;
}
g<<sol<<' ';
for(i=1;i<=n;++i)
{
v[i]=(sol/a[i].t)*a[i].c;
}
sort(v+1,v+n+1);
c=0;
for(i=n;i;--i)
{
c=c+v[i];
if(c>=m)
{
g<<i<<'\n';
return 0;
}
}
return 0;
}