제출 #534913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
534913		christinelynn	A Huge Tower (CEOI10_tower)	C++17	20 / 100	789 ms	262144 KiB

tower

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

const int N = 21;
int a[N], n, d, dp[N][(1<<N)];

ll rek(int pos, int msk){
  if(dp[pos][msk] != -1) return dp[pos][msk];
  if(__builtin_popcount(msk) == n-1){
    for(int i=0;i<n;i++)
    {
      if(msk & (1 << i)) continue;
      return dp[pos][msk] = a[i] <= a[pos] + d;
    }
  }
  ll ret = 0;
  for(int i=0;i<n;i++){
    if(msk & (1 << i)) continue;
    if(a[i] <= a[pos] + d)
      ret += rek(i, msk | (1 << i));
  }
  return dp[pos][msk] = ret;
}

int main(){
  cin.tie(0) -> ios_base::sync_with_stdio(0);

  memset(dp, -1, sizeof dp);
  cin >> n >> d;
  for(int i=0;i<n;i++) cin >> a[i];
  sort(a, a+n);
  ll ans = 0;
  for(int i=0;i<n;i++)
    ans += rek(i, (1<<i));
  cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5