Submission #590505

#	Time	Username	Problem	Language	Result	Execution time	Memory
590505		nodal_tree	A Huge Tower (CEOI10_tower)	C++17	15 / 100	276 ms	7548 KiB

tower

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 9;
int main() {
  int N; int D; cin >> N >> D; int dp[N + 1]; int top[N + 1]; int a[N + 1];
  a[0] = 0; dp[0] = 1; top[0] = 0;
  for(int i = 1; i<=N; i++){
     cin >> a[i]; dp[i] = 1; top[i] = 0;
  }
  sort(a, a + N);
  int l = 1;
  for(int r = 1; r<=N; r++){
    while(a[r] - a[l] > D){
      l++;
    }
    top[r] = r - l;
  }
  for(int i = 1; i<=N; i++){
    dp[i] = (dp[i - 1] * 1LL * (1LL * top[i] + 1LL* 1)) % MOD;
  }
  cout << dp[N] << '\n';
  return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 5 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 5 / 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