oj.uz

Submission #713053

# Submission time Handle Problem Language Result Execution time Memory
713053 2023-03-21T02:05:29 Z Narka A Huge Tower (CEOI10_tower) C++14
90 / 100
 1000 ms 9940 KB 
# include<bits/stdc++.h>
using namespace std ;
# define F first
# define S second
# define int long long
# define in insert
# define pb push_back
# define pob pop_back
# define INF INT_MAX
# define INFL 1e18 + 10
# define mod 1000000009	
# define vi vector<int>
# define pii pair<int , int>
# define vvi vector< vector<int> >
# define vpi vector<pair<int, int>> 
# define all(v) v.begin() , v.end()
# define debug(x) cerr << '\n' << #x << " = " << x << '\n' ;
# define rep( i , s , e ) for( int i = s ; i <= e ; i++ )
# define repR( i , e , s ) for( int i = e ; i >= s ; i-- )
# define trav(a) for(auto& x : a)
# define bk back()
# define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
# define endl "\n"
# define vva2 vector<vector<array<int, 2>>>

void solve(){
	int n, d;
	cin >> n >> d;
	vi a(n), ans(n);
	for(auto& x : a) cin >> x;
	sort(all(a));
	ans[0] = 1;
	rep(i, 1, n-1){
		int cnt = 1, j = i-1;
		while(j >= 0 && a[j] >= a[i] - d){
			cnt++;
			j--;
		}
		ans[i] = (ans[i-1] * 1LL * cnt) % mod;
	}
	cout << ans[n-1] << endl;

}

signed main() {	
//	FAST
	solve();
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

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

Subtask #17
5.0 / 5.0

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

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 980 KB Output is correct
2 Correct 852 ms 1076 KB Output is correct

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 4300 KB Output is correct
2 Execution timed out 1084 ms 4180 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 9940 KB Time limit exceeded
2 Halted 0 ms 0 KB -