解答の基本的な方針は公式解説の解法1と同じです。
公式解説の解法ではFenwick treeを使い計算量を\(O(N\log\max(A))\)とすることでTLEを回避していましたが、この解法では計算量を\(O(N^2)\)としたまま計算機の最適化によりTLEを回避しています。
具体的にはアーキテクチャにskylake-avx512、最適化オプションに03を設定し、\(O(N^2)\)回の計算を行う部分を足し算などの簡単な演算のみにすることでACすることができます。
実装例