oj.uz

Submission #481332

# Submission time Handle Problem Language Result Execution time Memory
481332 2021-10-20T12:07:06 Z Markadiusz Kangaroo (CEOI16_kangaroo) C++17
6 / 100
 1 ms 204 KB 
#include <bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

int main() {
        cin.tie(0)->sync_with_stdio(0);

        const long long mod = 1e9 + 7;
        int n, cs, cf;
        cin >> n >> cs >> cf;
        debug(n, cs, cf);
        if (cs > cf) {
                swap(cs, cf);
        }
        debug(cs, cf);
        vector dp(n + 1, vector(n + 1, 0));
        dp[1][1] = 1;
        FOR(i, 1, n - 1) {
                FOR(j, 1, n - 1) {
                        if (i + 1 == cs || i + 1 == cf) {
                                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j]) % mod;
                                dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
                        }
                        else if (i < cs) {
                                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * (j + 1)) % mod;
                                dp[i + 1][j - 1] = (dp[i + 1][j - 1] + dp[i][j] * (j - 1)) % mod;
                        }
                        else if (i < cf) {
                                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * j) % mod;
                                dp[i + 1][j - 1] = (dp[i + 1][j - 1] + dp[i][j] * (j - 1)) % mod;
                        }
                        else { // i >= cf
                                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * (j - 1)) % mod;
                                dp[i + 1][j - 1] = (dp[i + 1][j - 1] + dp[i][j] * (j - 1)) % mod;
                        }
                }
        }
        debug(dp);
        cout << dp[n][1] << endl;

}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -