結果

問題 No.1623 三角形の制作
ユーザー lam6er
提出日時 2025-03-20 20:40:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 199 ms / 2,000 ms
コード長 1,747 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 149,836 KB
最終ジャッジ日時 2025-03-20 20:40:49
合計ジャッジ時間 4,565 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr +=1
    
    max_val = 3000
    
    # Read red, green, blue arrays
    red = list(map(int, input[ptr:ptr+n]))
    ptr +=n
    green = list(map(int, input[ptr:ptr+n]))
    ptr +=n
    blue = list(map(int, input[ptr:ptr+n]))
    ptr +=n
    
    # Count frequencies
    red_count = [0] * (max_val + 1)
    for num in red:
        red_count[num] +=1
    
    g_count = [0] * (max_val + 1)
    for num in green:
        if num <= max_val:
            g_count[num] +=1
    
    b_count = [0] * (max_val + 1)
    for num in blue:
        if num <= max_val:
            b_count[num] +=1
    
    # Compute prefix sum for b_count
    pre_b = [0] * (max_val + 1)
    pre_b[0] = b_count[0]
    for y in range(1, max_val +1):
        pre_b[y] = pre_b[y-1] + b_count[y]
    
    # Precompute sum_pair[a] for all a from 0 to max_val
    sum_pair = [0] * (max_val +1)
    
    for a in range(max_val +1):
        total =0
        for x in range(a +1):
            g_freq = g_count[x]
            if g_freq ==0:
                continue
            y_min = a - x +1
            if y_min <0:
                y_min =0
            if y_min >a:
                # no y in blue <=a satisfies y >= y_min
                continue
            # sum b_count[y] for y >= y_min and <=a
            sum_b = pre_b[a]
            if y_min >0:
                sum_b -= pre_b[y_min -1]
            total += g_freq * sum_b
        sum_pair[a] = total
    
    # Compute the final answer
    result =0
    for a in range(max_val +1):
        if red_count[a] >0:
            result += red_count[a] * sum_pair[a]
    
    print(result)

if __name__ == "__main__":
    main()
0