oj.uz

Submission #535812

# Submission time Handle Problem Language Result Execution time Memory
535812 2022-03-11T10:23:54 Z makanhulia A Huge Tower (CEOI10_tower) C++17
20 / 100
 1000 ms 13300 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll mod = 1e9+9;

vector<ll>v;
vector<ll>tmp;
vector<bool>mark;
ll n, d;

ll f(int idx, ll last){
    if(idx == n){
        return 1;
    }

    ll ret = 0;

    for(int i = 0; i < n; i++){
        if(!mark[i] && (v[i] <= last + d)){
            //cout << "can stack " << v[i] << " on top of " << last << endl;
            mark[i] = true;
            tmp.push_back(v[i]);
            ret += f(idx + 1, v[i]);
            mark[i] = false;
            tmp.pop_back();
        }
    }

    return (ret % mod);
}

int main(){
    cin >> n >> d;

    for(int i = 0; i < n; i++){
        ll x; cin >> x;
        v.push_back(x);
        mark.push_back(0);
    }

    cout << (f(0, 1e9) % mod) << endl;

    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 1 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

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

Subtask #13
0 / 5.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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

Subtask #20
0 / 5.0

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