Break through in 2 minutes. Just write.
X, Y = map(int, input().split())
if Y < X:
X, Y = Y, X
if X + 3 > Y:
print('Yes')
else:
print('No')
Break through in 2 minutes. Just write.
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
if sum(a * b for a, b in zip(A, B)) == 0:
print('Yes')
else:
print('No')
Break through in 7 minutes. N ≤ 16, so even if you run the tournament obediently, it will not TLE with * O * (2 17 ), so do it obediently AC.
N, *A = map(int, open(0).read().split())
a = range(2 ** N)
while len(a) != 2:
t = []
for i in range(0, len(a), 2):
if A[a[i]] > A[a[i + 1]]:
t.append(a[i])
else:
t.append(a[i + 1])
a = t
if A[a[0]] > A[a[1]]:
print(a[1] + 1)
else:
print(a[0] + 1)
After the contest, I divided the mountain into two in the middle and realized that the strongest one on the side without the strongest one was the runner-up, so I couldn't solve it quickly.
N, *A = map(int, open(0).read().split())
i = A.index(max(A))
if i < 2 ** (N - 1):
print(A.index(max(A[:2 ** (N - 1)]) + 1)
else:
print(A.index(max(A[2 ** (N - 1):]) + 1)
It broke through in 13 minutes. The moment I saw the problem statement, I thought I was lucky to have one imos method, but I was indignant when I saw b i ≤ 10 9 . I was surprised to find that there was no problem when I simulated the method in my brain. AC. It seems that sitting pressure was fine. Let's solve it later.
from sys import stdin
readline = stdin .readline
N, C = map(int, readline().split())
d = {}
for _ in range(N):
a, b, c = map(int, readline().split())
d.setdefault(a, 0)
d[a] += c
d.setdefault(b + 1, 0)
d[b + 1] -= c
skeys = sorted(d)
for i in range(1, len(skeys)):
d[skeys[i]] += d[skeys[i - 1]]
for k in d:
if d[k] > C:
d[k] = C
result = 0
for i in range(len(skeys) - 1):
result += d[skeys[i]] * (skeys[i + 1] - skeys[i])
print(result)
Postscript: I tried to solve it by coordinate compression + imos method.
from sys import stdin
from itertools import accumulate
readline = stdin .readline
N, C = map(int, readline().split())
abc = [tuple(map(int, readline().split())) for _ in range(N)]
p = set()
for a, b, _ in abc:
p.add(a)
p.add(b)
p.add(b + 1)
inv = sorted(p)
fwd = {}
for i in range(len(inv)):
fwd[inv[i]] = i
t = [0] * len(inv)
for a, b, c in abc:
t[fwd[a]] += c
t[fwd[b + 1]] -= c
t = list(accumulate(t))
result = 0
for i in range(len(t) - 1):
result += min(t[i], C) * (inv[i + 1] - inv[i])
print(result)
Postscript: I tried to solve it by the method described in the commentary. Hmm, smart.
from sys import stdin
readline = stdin .readline
N, C = map(int, readline().split())
q = []
for _ in range(N):
a, b, c = map(int, readline().split())
q.append((a, c))
q.append((b + 1, -c))
result = 0
p = 0
ac = 0
for x, y in sorted(q):
result += min(C, ac) * (x - p)
p = x
ac += y
print(result)
Break through in 67 minutes. WA2. The moment I read the problem statement, I knew that I should do it from behind, but for some reason I used Union Find to manage it and self-destructed.
from sys import stdin
readline = stdin.readline
N, M = map(int, readline().split())
A = list(map(int, readline().split()))
links = [[] for _ in range(N)]
for _ in range(M):
X, Y = map(lambda x: int(x) - 1, readline().split())
links[X].append(Y)
maxvs = [None] * N
result = -(10 ** 18)
for i in range(N - 1, -1, -1):
if len(links[i]) == 0:
maxvs[i] = A[i]
continue
maxv = max(maxvs[j] for j in links[i])
result = max(result, maxv - A[i])
maxvs[i] = max(maxv, A[i])
print(result)
Postscript: It was okay to do it from before, and I feel that this is easier to understand.
from sys import setrecursionlimit, stdin
from functools import lru_cache
setrecursionlimit(10 ** 6)
readline = stdin.readline
N, M = map(int, readline().split())
A = list(map(int, readline().split()))
links = [[] for _ in range(N)]
for _ in range(M):
X, Y = map(lambda x: int(x) - 1, readline().split())
links[X].append(Y)
@lru_cache(maxsize=None)
def dfs(x):
result = A[x]
for y in links[x]:
result = max(result, dfs(y))
return result
result = -(10 ** 18)
for i in range(N):
if len(links[i]) == 0:
continue
result = max(result, max(dfs(j) for j in links[i]) - A[i])
print(result)
I went to WA2 but couldn't break through. Should I have done it with memoization recursion instead of Greedy? (Y-1) ÷ 2 was prioritized, but (Y + 1) ÷ 2 was sometimes better. It seems. I knew by doing a similar problem somewhere that it was better to change Y instead of changing X.
from functools import lru_cache
X, Y = map(int, input().split())
@lru_cache(maxsize=None)
def f(y):
if X >= y:
return abs(X - y)
if y % 2 == 0:
return min(abs(y - X), f(y // 2) + 1)
else:
return min(abs(y - X), f((y - 1) // 2) + 2, f((y + 1) // 2) + 2)
print(f(Y))
Recommended Posts