oj.uz

Submission #639824

# Submission time Handle Problem Language Result Execution time Memory
639824 2022-09-12T05:16:04 Z Joshc Fancy Fence (CEOI20_fancyfence) PyPy 3
0 / 100
 49 ms 19788 KB 
import sys, collections
input = sys.stdin.readline

n = int(input())
h = [*map(int, input().split())]
w = [*map(int, input().split())]
parent = [1 for i in range(n)]
sz = [1] * n
ans = 0

def root(x):
    if x == parent[x]:
        return parent[x]
    parent[x] = root(parent[x])
    return parent[x]

def join(x, y):
    global ans
    x, y = root(x), root(y)
    if x == y:
        return
    ans += w[x]*w[y]
    if sz[x] > sz[y]:
        x, y = y, x
    parent[x] = y
    sz[y] += sz[x]
    w[y] += w[x]

d = collections.defaultdict(list)
for i in range(n):
    d[h[i]].append(i)

res = 0
added = [False]*n
heights = sorted(d.keys(), reverse=True) + [0]
for height, nextheight in zip(heights, heights[1:]):
    for i in d[height]:
        ans += w[i]*(w[i]+1)//2
        added[i] = True
        if i and added[i-1]:
            join(i-1, i)
        if i+1 < n and added[i+1]:
            join(i, i+1)
    res += ans * (height*(height+1)//2 - nextheight*(nextheight+1)//2)

print(res)

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 18732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 18564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 18580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 19788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 18608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 18628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 18732 KB Output isn't correct
2 Halted 0 ms 0 KB -