第二回全国統一プログラミング王決定戦本戦 A Count Triplets
感想
愚直解でTLEだしたあと、真ん中を動かしながら前後の数をカウントすればO(N^2)で解けることに気づいた。自力で解けたのがわれながら進歩したなと思ってる。
提出予定コード
#include <bits/stdc++.h> using namespace std; int main(){ int N; cin>>N; int A[N]; for(int i=0;i<N;i++){ cin>>A[i]; } long long cnt=0; long long pre=0; long long post=0; for(int i=1;i<N-1;i++){ pre=0; post=0; for(int j=0;j<i;j++){ if(A[j]<A[i]) pre++; } for(int k=i+1;k<N;k++){ if(A[k]<A[i]) post++; } cnt+=(pre*post); } cout<<cnt<<endl; return 0; }