Submission #127484

#TimeUsernameProblemLanguageResultExecution timeMemory
127484RockyBTents (JOI18_tents)C++17
100 / 100
367 ms35836 KiB
#include <bits/stdc++.h> #define rep(a, b, c) for (int a = (b); (a) <= (c); a++) #define per(a, b, c) for (int a = (b); (a) >= (c); a--) #define nl '\n' #define ioi exit(0); const int mod = (int)1e9 + 7; const int N = (int)1e4; using namespace std; void add(int &x, int y) { x += y; if (x >= mod) x -= mod; if (x < 0) x += mod; } int sum(int x, int y) { add(x, y); return x; } int n, m; int dp[3001][3001]; int calc(int v = n, int free = m) { if (!v) return 1; if (~dp[v][free]) return dp[v][free]; int res = calc(v - 1, free); // put < or > or ^ or v if (free > 0) { add(res, calc(v - 1, free - 1) * 1ll * free * 4 % mod); // connect v and ^ if (v > 1) add(res, calc(v - 2, free - 1) * 1ll * (v - 1) * free % mod); } // connect > and < if (free > 1) add(res, calc(v - 1, free - 2) * 1ll * (free * (free - 1) / 2) % mod); return dp[v][free] = res; } int main() { #ifdef IOI freopen ("in.txt", "r", stdin); freopen ("slow.out", "w", stdout); #endif cin >> n >> m; memset(dp, -1, sizeof(dp)); int ans = sum(calc(), -1); cout << ans << nl; ioi } /* 5116 0 3720 1 450 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...