C++(clang++11) 解法, 执行用时: 157ms, 内存消耗: 2748K, 提交时间: 2020-10-25 21:34:17

#include<bits/stdc++.h>
using namespace std;
const int _=1e5+5;
long long n,L,R,a[_],l[_],r[_],sum;
int check(long long k)
{
	long long x=0,y=0;
	for(int i=1;i<=n;++i)
	{
		long long s=min(a[i]/k,r[i]);
		if(s<l[i])
		return 0;
		x+=s;
		if(s<r[i])
		{
			y+=a[i]%k;
			if(y>=k)
			y-=k,++x; 
		}
	}
	return x>=L;
}
int main()
{
	cin>>n>>L>>R;
	for(int i=1;i<=n;++i)
	cin>>a[i];
	for(int i=1;i<=n;++i)
	cin>>l[i]>>r[i],sum+=l[i];
	if(sum>R)
	cout<<0<<endl,exit(0);
	long long l=0,r=1e18;
	while(l<r)
	{
		long long mid=(l+r)>>1;
		if(check(mid+1))
		l=mid+1;
		else
		r=mid;
	}
	cout<<l<<endl;
	return 0;
}

pypy3(pypy3.6.1) 解法, 执行用时: 587ms, 内存消耗: 32048K, 提交时间: 2020-10-25 14:28:57

INF=0x3FFFFFFFFFFFFFFF

def check(num):
    last=0
    for i in range(n):
        if x[i]*num>a[i]:
            return False
        last+=min((y[i]-x[i])*num,a[i]-x[i]*num)
    return last>=(need-Sum)*num

n,need,lim=map(int,input().split())
a=list(map(int,input().split()))
x=[]
y=[]
Sum=0
for i in range(n):
    tmpx,tmpy=map(int,input().split())
    x.append(tmpx)
    y.append(tmpy)
    Sum+=x[i]
if Sum>lim:
    print(0)
    exit()
L=0
R=INF
mid=0
while L+1<R:
    mid=(L+R)//2
    if check(mid):
        L=mid
    else:
        R=mid
print(L)