oj.uz

Submission #531261

# Submission time Handle Problem Language Result Execution time Memory
531261 2022-02-28T09:36:06 Z hohohaha A Huge Tower (CEOI10_tower) C++14
45 / 100
 330 ms 82372 KB 
#include<bits/stdc++.h>
using namespace std;
#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); i++) 
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' '
#define int long long
const int maxn = 3e6 + 5, mod = 1e9 + 9; 
int n, d; 
int arr[maxn]; 
int dp[1 << 20][20]; 
signed main() { 
//	freopen("tower.inp", "r", stdin); 
//	freopen("tower.out", "w", stdout); 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	cin >> n >> d; 
	fori(i, 0, n - 1) cin >> arr[i]; 
	fori(i, 0, n - 1) dp[1 << i][i] = 1; 
	fori(mask, 1, (1 << n) - 1) { 
		fori(last, 0, n - 1) { 
			if(mask >> last & 1) { 
				fori(nxt, 0, n - 1) { 
					if(!(mask >> nxt & 1)) { 
						if(arr[nxt] <= arr[last] + d) { 
							dp[mask ^ (1 << nxt)][nxt] += dp[mask][last]; 
							if(dp[mask ^ (1 << nxt)][nxt] >= mod) dp[mask ^ (1 << nxt)][nxt] -= mod; 
						}
					}
				}
			}
		}
	}
	int ans = 0; 
	fori(last, 0, n - 1) (ans += dp[(1 << n) - 1][last]) %= mod; 
	cout << ans; 
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 580 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 1908 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 7024 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 16432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -