結果

問題 No.1623 三角形の制作
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:30:29
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 183 ms / 2,000 ms
コード長 1,390 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 265 ms
コンパイル使用メモリ 96,104 KB
実行使用メモリ 140,196 KB
最終ジャッジ日時 2026-07-07 09:24:03
合計ジャッジ時間 5,457 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n = int(input())
r = list(map(int, input().split()))
g = list(map(int, input().split()))
b = list(map(int, input().split()))

max_val = 3000  # As per the problem constraints

# Frequency counts for green and blue sticks
count_g = [0] * (max_val + 1)
for x in g:
    count_g[x] += 1

count_b = [0] * (max_val + 1)
for y in b:
    count_b[y] += 1

# Prefix sum array for blue sticks
prefix_b = [0] * (max_val + 2)
for y in range(max_val + 1):
    prefix_b[y + 1] = prefix_b[y] + count_b[y]

# Frequency dictionary for red sticks
from collections import defaultdict
freq = defaultdict(int)
for x in r:
    freq[x] += 1

answer = 0

for R in freq:
    # Ensure R does not exceed max_val to prevent index errors
    current_R = min(R, max_val)
    total_pairs = 0
    # Iterate through possible x values (green sticks)
    for x in range(current_R + 1):
        if count_g[x] == 0:
            continue  # Skip if no green sticks of this length
        a = current_R - x + 1
        a = max(a, 0)
        if a > current_R:
            continue  # No valid blue sticks
        # Calculate the sum of blue sticks from a to current_R
        # Using prefix_b which is 1-based for the ranges
        sum_b = prefix_b[current_R + 1] - prefix_b[a]
        total_pairs += count_g[x] * sum_b
    # Add the contributions from all red sticks of length R
    answer += total_pairs * freq[R]

print(answer)
0