oj.uz

Submission #759878

# Submission time Handle Problem Language Result Execution time Memory
759878 2023-06-17T01:55:25 Z Asamai Kangaroo (CEOI16_kangaroo) C++17
100 / 100
 18 ms 14108 KB 
#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second
// #define     int                   long long

typedef     long long             ll;
typedef     unsigned long long    ull;
typedef     double                db;
typedef     long double           ld;
typedef     pair<db, db>          pdb;
typedef     pair<ld, ld>          pld;
typedef     pair<int, int>        pii;
typedef     pair<ll, ll>          pll;
typedef     pair<ll, int>         plli;
typedef     pair<int, ll>         pill;

const int MAX_N = 2e3 + 5;
const int mod = 1e9 + 7; // 998244353

int n, s, t;
int dp[MAX_N][MAX_N];

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> s >> t;
	dp[1][1] = 1;

	int cnt = 0;

	for (int i = 1; i < n; i++) {
		if (i == s || i == t) cnt++;
		for (int j = 1; j <= i; j++) {
			if (!dp[i][j]) continue;

			if (i + 1 == s || i + 1 == t) {
				// tao ra 1 tplt rieng
				(dp[i + 1][j + 1] += dp[i][j]) %= mod;

				// ghep vao 1 tplt
				(dp[i + 1][j] += dp[i][j]) %= mod;
			}
			else {
				// tao ra 1 tplt rieng -> j + 1 - cnt vi tri
				if (j + 1 - cnt > 0) {
					(dp[i + 1][j + 1] += 1ll * dp[i][j] * (j + 1 - cnt) % mod) %= mod;
				}

				// ket noi 2 tlpt nao do -> j - 1 vi tri
				(dp[i + 1][j - 1] += 1ll * dp[i][j] * (j - 1) % mod) %= mod;				
			}
		}

	}

	cout << dp[n][1];

	return 0;
}

/*


*/

Subtask #1
6.0 / 6.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 1 ms 452 KB Output is correct
11 Correct 1 ms 468 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 1 ms 452 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 1096 KB Output is correct
13 Correct 1 ms 1108 KB Output is correct
14 Correct 1 ms 1108 KB Output is correct
15 Correct 1 ms 1108 KB Output is correct
16 Correct 1 ms 1104 KB Output is correct
17 Correct 1 ms 1108 KB Output is correct
18 Correct 2 ms 1108 KB Output is correct
19 Correct 1 ms 1092 KB Output is correct
20 Correct 1 ms 1108 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 1 ms 452 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 1096 KB Output is correct
13 Correct 1 ms 1108 KB Output is correct
14 Correct 1 ms 1108 KB Output is correct
15 Correct 1 ms 1108 KB Output is correct
16 Correct 1 ms 1104 KB Output is correct
17 Correct 1 ms 1108 KB Output is correct
18 Correct 2 ms 1108 KB Output is correct
19 Correct 1 ms 1092 KB Output is correct
20 Correct 1 ms 1108 KB Output is correct
21 Correct 3 ms 3796 KB Output is correct
22 Correct 5 ms 4076 KB Output is correct
23 Correct 4 ms 4436 KB Output is correct
24 Correct 18 ms 14108 KB Output is correct
25 Correct 18 ms 14100 KB Output is correct
26 Correct 18 ms 14088 KB Output is correct
27 Correct 18 ms 14032 KB Output is correct
28 Correct 11 ms 10188 KB Output is correct