Submission #534915

#	Time	Username	Problem	Language	Result	Execution time	Memory
534915		devariaota	A Huge Tower (CEOI10_tower)	C++17	0 / 100	133 ms	262148 KiB

tower

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

const int N = 21, M = 1e9 + 9;
int a[N], n, d;
ll 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 = (ret + rek(i, msk | (1 << i))) % M;
  }
  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 = (ans + rek(i, (1<<i))) % M;
  cout << ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 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