結果

問題 No.3128 Isosceles Triangle
コンテスト
ユーザー GOTKAKO
提出日時 2025-04-25 21:38:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 426 ms / 2,500 ms
コード長 731 bytes
コンパイル時間 2,733 ms
コンパイル使用メモリ 207,680 KB
実行使用メモリ 21,128 KB
最終ジャッジ日時 2025-04-25 21:39:28
合計ジャッジ時間 8,075 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<int> A(N);
    for(auto &a : A) cin >> a;
    sort(A.begin(),A.end());

    long long answer = 0,aoi = 0,akane = 0;
    map<int,long long> M;
    priority_queue<int,vector<int>,greater<>> Q;
    for(auto a : A){
        if(M.count(a) == false) Q.push(a);
        while(Q.size()){
            int b = Q.top();  
            if(b+b <= a) Q.pop(),aoi -= M[b]*(M[b]-1)/2;
            else break;
        }
        answer += aoi; answer += (akane-M[a])*M[a];
        aoi += M[a]; M[a]++; akane++;
    }
    for(auto [k,v] : M) answer -= v*(v-1)*(v-2)/6;
    cout << answer << endl;
}
0