P1083

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
n,m=map(int,input().split())
day=list(map(int,input().split()))
rent_d=[]
rent_n=[]
for i in range(m):
    a,b,c=map(int,input().split())
    rent_n.append(a)
    rent_d.append([b,c])

def check(x):
    d=[0 for i in range(n)]
    for i in range(x):
        d[rent_d[i][0]-1]+=rent_n[i]
        if(rent_d[i][1]>n-1):
            d[n-1]=d[n-1]
        else:
            d[rent_d[i][1]]-=rent_n[i]
    sum=[0 for i in range(n)]
    for i in range(n):
        if(i==0):
            sum[i]=d[i]
        else:
            sum[i]=sum[i-1]+d[i]
        if(sum[i]>day[i]):
            return False
    return True

l,r=0,m-1
while(l+1<r):
    mid=(l+r)//2
    if(check(mid)):
        l=mid
    else:
        r=mid

if(r==1 and l==0):
    print('0')
else:
    print('-1')
    print(l+1)

P1314

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
n,m,s=map(int,input().split())
w=[]
v=[]
sw=list(0 for i in range(n))
sv=list(0 for i in range(n))
sm=[]
weight,value=0,0
ans=1e18
for i in range(n):
    weight,value=map(int,input().split())
    w.append(weight)
    v.append(value)

for i in range(m):
    sm.append(list(map(int,input().split())))
def check(x):
    global ans
    sum=0
    for i in range(n):
        if(w[i]>=x):
            if(i>0):
                sw[i]=sw[i-1]+1
                sv[i]=sv[i-1]+v[i]
            else:
                sw[i]=1
                sv[i]=v[i]
        else:
            if(i>0):
                sw[i]=sw[i-1]
                sv[i]=sv[i-1]
            else:
                sw[i]=0
                sv[i]=0
    for i in range(m):
        if((sm[i][0]-2)>=0):
            l=sm[i][0]-2
            r=sm[i][1]-1
            sum+=(sw[r]-sw[l])*(sv[r]-sv[l])
        else:
            l=0
            r=sm[i][1]-1
            sum+=sw[r]*sv[r]
    ans=min(ans,abs(sum-s))
    return sum<=s

lt,rt=0,max(w)
while(lt+1<rt):
    mid=(lt+rt)//2
    if(check(mid)):
        rt=mid
    else:
        lt=mid
print(ans)

P2249

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n,m=map(int, input().split())
ls1=list(map(int,input().split()))
ls2=list(map(int,input().split()))
l=0
r=n-1
ans=0
for i in range(m):
    x=ls2[i]
    while(l+1<r):
        if(ls1[(l+r)//2]>=x):
            r=(l+r)//2
        else:
            ans=(l+r)//2
            l=(l+r)//2
    if(ls1[ans]==x):
        print(ans+1,end=" ")
    elif(ls1[ans+1]==x):
        print(ans+2,end=" ")
    else:
        print(-1,end=" ")

P2440

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n,k=map(int,input().split())
ls=[]
ans=0
for i in range(n):
    ls.append(int(input()))

def check(x): 
    y=0
    for i in range(n):
        y+=ls[i]//x
    return y>=k
l=0
r=max(ls)
while(l+1<r):
    mid=(l+r)//2
    if(check(mid)):
        ans=mid
        l=mid
    else:
        r=mid
print(ans)