Submission #499607

#	Time	Username	Problem	Language	Result	Execution time	Memory
499607		cmsgr8er	A Huge Tower (CEOI10_tower)	C++17	100 / 100	274 ms	16004 KiB

tower

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5