提出 #31870777

---

ソースコード 拡げる

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

int main()
{
  int n;
  cin >> n;

  map<int, int> m;
  for (int i = 0; i < n; i++){
    int a;
    cin >> a;
    if (m.count(a) == 0){
      m.insert(make_pair(a, 1));
    } else {
      m[a]++;
    }
  }

  // dp0[i] : i 番目の整数の個数
  int m1 = m.size();
  vector<ll> dp0(m1);
  {
    int i = 0;
    for (auto it = m.begin(); it != m.end(); it++){
      auto [x, ct] = *it;
      dp0[i++] = ct;
    }
  }

  // dp1[i] : i 番目の整数までに １つ目を選ぶ時の選び方
  vector<ll> dp1(m1);
  dp1[0] = dp0[0];
  for (int i = 1; i < m1; i++){
    dp1[i] = dp1[i-1] + dp0[i];
  }

  // dp2[i] : i 番目の整数までに ２つ目を選ぶ時の選び方
  vector<ll> dp2(m1);
  dp2[0] = 0;
  for (int i = 1; i < m1; i++){
    dp2[i] = dp0[i] * dp1[i-1] + dp2[i-1];
  }
  
  // dp3[i] : i 番目の整数までに ３つ目を選ぶ時の選び方
  vector<ll> dp3(m1);
  dp3[0] = dp3[1] = 0;
  for (int i = 2; i < m1; i++){
    dp3[i] = dp0[i] * dp2[i-1] + dp3[i-1];
  }

  /*
  for (ll x : dp0){ cout << x << " " << endl; }
  cout << endl;
  for (ll x : dp1){ cout << x << " " << endl; }
  cout << endl;
  for (ll x : dp2){ cout << x << " " << endl; }
  cout << endl;
  for (ll x : dp3){ cout << x << " " << endl; }
  cout << endl;
  */
  
  ll ans = dp3[m1 - 1];
  cout << ans << endl;
  
  return 0;
}

提出情報

ジャッジ結果