oj.uz

Submission #499607

# Submission time Handle Problem Language Result Execution time Memory
499607 2021-12-29T02:42:36 Z cmsgr8er A Huge Tower (CEOI10_tower) C++17
100 / 100
 274 ms 16004 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
	long long n,d, K=1e9+9; cin >> n >> d;
	vector<long long> h(n); for (int i=0; i<n; i++) cin >> h[i];
	sort(h.begin(), h.end());
	vector<long long> dp(n); dp[0] = 1;
	for (int i=1; i<n; i++) {
		int lo = lower_bound(h.begin(), h.end(), h[i]-d)-h.begin();
		long long ok = i-lo;
		dp[i] = (dp[i-1]*(ok+1))%K;
	}
	cout << dp[n-1];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 272 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 272 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 460 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1436 KB Output is correct
2 Correct 25 ms 1428 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 6564 KB Output is correct
2 Correct 117 ms 6572 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 16004 KB Output is correct
2 Correct 274 ms 15352 KB Output is correct