結果

問題 No.3128 Isosceles Triangle
ユーザー tkykwtnb
提出日時 2025-04-26 05:10:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 540 ms / 2,500 ms
コード長 757 bytes
コンパイル時間 398 ms
コンパイル使用メモリ 81,932 KB
実行使用メモリ 205,196 KB
最終ジャッジ日時 2025-04-26 05:10:15
合計ジャッジ時間 10,711 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
from bisect import bisect_left,bisect_right
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N=int(input())
A=list(map(int,input().split()))
keys=set()
D=defaultdict(list)
for i,a in enumerate(A):
    D[a].append(i)
    keys.add(a)
keys=sorted(keys)
cumsum=[0]
for key in keys:
    cumsum.append(cumsum[-1]+len(D[key]))
AA=[]
for k,v in D.items():
    if len(v)>=2:AA.append(k)
ans=0
for a in AA:
    ans+=cmb(len(D[a]),2)*cumsum[bisect_left(keys,a)]
    ans+=cmb(len(D[a]),2)*(cumsum[bisect_left(keys,a*2)]-cumsum[bisect_right(keys,a)])
print(ans)
0