oj.uz

Submission #900589

# Submission time Handle Problem Language Result Execution time Memory
900589 2024-01-08T15:19:45 Z warner1129 Kangaroo (CEOI16_kangaroo) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
 
using namespace std;

#ifdef LOCAL
template<class... T> void dbg(T... x) { char e{}; ((cerr << e << x, e = ' '), ...); }
#define debug(x...) dbg(#x, '=', x, '\n')
#else
#define debug(...) ((void)0)
#endif
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
 
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
 
template<class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
constexpr int mod = 1e9 + 7, inv2 = (mod + 1) / 2;
 
template<class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }

void solve() {
    int n, s, t;
    cin >> n >> s >> t;

    bool op = s > 1;
    bool ed = t > 1;
    vector dp(n + 1, array<array<i64, 2>, 2>{});
    
    dp[1][0][0] = 1;
    for (int i = 2; i <= n; i++) {
        decltype(dp) f(n + 1);
        // vector<i64> f(n + 1);
        
        for (int j = 1; j < i; j++) {
            if (i == s) {
                f[j][0][0] += dp[j][0][0];
                f[j][0][1] += dp[j][0][1];
            } else if (i == t) {
                f[j][0][0] += dp[j][0][0];
                f[j][1][0] += dp[j][1][0];
            } else {
                for (int x : {0, 1})
                    for (int y : {0, 1}) {
                        f[j - 1][x][y] += dp[j][x][y] * (j - 1);
                        f[j + 1][x][y] += dp[j][x][y] * (i - 1 - j + op + ed);
                        if (!op and x == 0) f[j][1][y] += dp[j][0][y];
                        if (!ed and y == 0) f[j][x][1] += dp[j][x][0];
                        
                    }
            }
        }

        if (s == i) op = false;
        if (t == i) ed = false;
        
        dp.swap(f);

        for (int j = 0; j <= n; j++)
            for (int x : {0, 1})
                for (int y : {0, 1})
                    dp[j][x][y] %= mod;
        debug(i, dp);
    }

    cout << (dp[1][0][0] + dp[1][0][1] + dp[1][1][0] + dp[1][1][1]) << '\n';
}
 
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 49.0

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