Submission #19679362


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);i++)

// #define LOCAL 1;
#ifdef LOCAL
#define dbg(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define dbg(x) true
#endif

template<typename T>
ostream& operator<< (ostream& out, const vector<T>& v) {
  out << "[";
  size_t last = v.size() - 1;
  for (size_t i = 0; i < v.size(); ++i) {
    out << v[i];
    if (i != last)
      out << ", ";
  }
  out << "]";
  return out;
}

template<typename F, typename S>
ostream& operator<< (ostream& out, const pair<F,S>& p) {
  out << "[" << p.first << ", " << p.second << "]";
  return out;
}



int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll n;
  cin >> n;
  vector<ll> x(n);
  map<ll,ll> mpx;
  rep(i,n) cin >> x[i],mpx[x[i]]=i;
  vector<long double> dp(1<<n,INT_MAX);
  dp[0] = 0;
  rep(i,1<<n){
    set<ll> stx;
    rep(j,n){
      if((1LL<<j) & i) stx.insert(x[j]);
    }
    set<ll> stxx;
    for(auto j:stx){
      stxx.insert(j);
      stxx.insert(j-1);
      stxx.insert(j+1);
    }
    for(auto j:stxx){
      if(stx.count(j-1) && stx.count(j+1) && stx.count(j)){
        dp[i] = min(dp[i],(dp[i^(1<<mpx[j-1])] + dp[i^(1<<mpx[j])] + dp[i^(1<<mpx[j+1])] )/3. + 1.);
      }
      else if(stx.count(j-1) && stx.count(j)){
        dp[i] = min(dp[i], (dp[i^(1<<mpx[j-1])] + dp[i^(1<<mpx[j])])/2. + 3./2. );
      }
      else if(stx.count(j+1) && stx.count(j)){
        dp[i] = min(dp[i], (dp[i^(1<<mpx[j+1])] + dp[i^(1<<mpx[j])])/2. + 3./2. );
      }
      else if(stx.count(j+1) && stx.count(j-1)){
        dp[i] = min(dp[i], (dp[i^(1<<mpx[j+1])] + dp[i^(1<<mpx[j-1])])/2. + 3./2. );
      }
      else if(stx.count(j)){
        dp[i] = min(dp[i], dp[i^(1<<mpx[j])]+3);
      }
      else if(stx.count(j-1)){
        dp[i] = min(dp[i], dp[i^(1<<mpx[j-1])]+3);
      }
      else if(stx.count(j+1)){
        dp[i] = min(dp[i], dp[i^(1<<mpx[j+1])]+3);
      }
    }
  }

  cout << fixed << setprecision(8) << dp[(1<<n)-1] << endl;




  return 0;

}

Submission Info

Submission Time
Task J - ボール
User KawattaTaido
Language C++ (GCC 9.2.1)
Score 5
Code Size 2176 Byte
Status AC
Exec Time 174 ms
Memory 4148 KB

Judge Result

Set Name All
Score / Max Score 5 / 5
Status
AC × 6
Set Name Test Cases
All 00, 01, 02, 03, 90, 91
Case Name Status Exec Time Memory
00 AC 174 ms 4148 KB
01 AC 16 ms 3740 KB
02 AC 4 ms 3680 KB
03 AC 6 ms 3672 KB
90 AC 6 ms 3692 KB
91 AC 2 ms 3768 KB