503. 借教室 - AcWing題庫

n,m=map(int,input().split())
class_=list(map(int,input().split()))
class_=[0]+class_
d=[0]
s=[0]
t=[0]
for _ in range(m):
? ? dj,sj,tj=map(int,input().split())
? ? d.append(dj)
? ? s.append(sj)
? ? t.append(tj)

def check(k):
? ? b=[0]*(n+2)
? ? res=0
? ? for i in range(1,k+1):
? ? ? ? b[s[i]]+=d[i]
? ? ? ? b[t[i]+1]-=d[i]
? ? for i in range(1,n+1):
? ? ? ? res+=b[i]
? ? ? ? if res>class_[i]:
? ? ? ? ? ? return False
? ? return ?True

l,r=0,m
while(l<r):
? ? mid=l+r+1>>1
? ? if check(mid):
? ? ? ? l=mid
? ? else:
? ? ? ? r=mid-1
if (r==m):
? ? print(0)
else:
? ? print(-1)
? ? print(l+1)
?

?0技能升級 - 藍橋云課 (lanqiao.cn)

N,M=map(int,input().split())

a=[0]*N

b=[0]*N

for?i?in?range?(N):

????a[i],b[i]=map(int,input().split())

def?check(mid):

????res=0

????for?i?in?range?(N):

????????if?a[i]>=mid:

????????????res+=(a[i]-mid)//b[i]+1

????return?res>=M

?

l=0

r=10**6

while(l<r):

????mid=l+r+1>>1

????if?check(mid):

????????l=mid

????else:

????????r=mid-1

res=0

cnt=0

for?i?in?range(N):

????if?a[i]>r:

????????c=(a[i]-r)//b[i]+1

????????end=a[i]-(c-1)*b[i]

????????cnt+=c

????????res+=(a[i]+end)*c//2

print(res-(cnt-M)*r)

?