Submission #1146155

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1146155	2025-02-05 15:54:24	wikidere	Building Bridges (CEOI17_building)	Pypy 3	0 / 100	195 ms	84636 KiB

building

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
from collections import deque
def min_bridge_cost(n, h, w):
    # Prefix sum of w
    prefixW = [0] * n
    prefixW[0] = w[0]
    for i in range(1, n):
        prefixW[i] = prefixW[i - 1] + w[i]
    # dp[i] stores the minimum cost to reach pillar i
    dp = [float('inf')] * n
    dp[0] = 0  # Base case: first pillar is always included
    # Monotonic deque to optimize DP recurrence
    dq = deque([(0, 0)])  # Stores (index, dp value)
    def cost(i, j):
        """ Returns cost of moving from i to j """
        return (h[i] - h[j]) ** 2 + (prefixW[j - 1] - prefixW[i])
    for j in range(1, n):
        # Remove from deque if it's no longer optimal
        while len(dq) > 1 and cost(dq[0][0], j) >= cost(dq[1][0], j):
            dq.popleft()
        # Compute dp[j] using best available i
        best_i = dq[0][0]
        dp[j] = dp[best_i] + cost(best_i, j)
        # Maintain the deque
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stdout)

Compiling 'building.py'...

=======
  adding: __main__.pyc (deflated 36%)

=======

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40