oj.uz

답안 #835239

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
835239 2023-08-23T10:55:26 Z Ahmad_Elsisy 캥거루 (CEOI16_kangaroo) C++17
100 / 100
 54 ms 16212 KB 
#include <bits/stdc++.h>
using namespace std;


const int N = 2004, MOD = 1e9 + 7;
int memo[N][N], n;

int add(int a, int b) {
    a += b;
    while(a >= MOD)
        a -= MOD;
    while(a < 0)
        a += MOD;
    return a;
}

int mul(int a, int b) {
    return (1ll * (a % MOD) * (b % MOD)) % MOD;
}
int s, e;

int solve(int i, int j) {
    if(i == n + 1)
        return j == 1;
    int &ret = memo[i][j];
    if(~ret)
        return ret;
    bool putStart = (i > s);
    bool putEnd = (i > e);
    ret = 0;
    // add to comp
    if(i == s) {
        if(!(j == 1 && putEnd && i < n))
            ret = add(ret, solve(i + 1, j));
        ret = add(ret, solve(i + 1, j + 1));
        return ret;
    }
    if(i == e) {
        if(!(j == 1 && putStart && i < n))
            ret = add(ret, solve(i + 1, j));
        ret = add(ret, solve(i + 1, j + 1));
        return ret;
    }

    // new comp ?(x)?(y)?(z)?
    ret = add(ret, mul(max(0, j + 1 - putStart - putEnd), solve(i + 1, j + 1)));
    // merge two adjacent comps
    if(j > 1)
        ret = add(ret, mul(j - 1, solve(i + 1, j - 1)));
    return ret;
}
void solve() {
    cin >> n >> s >> e;
    memset(memo , -1 ,sizeof memo);
    cout << solve(1, 0) << "\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int tc = 1;
//    cin >> tc;
    while(tc--){
        solve();
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 8 ms 15928 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 8 ms 15928 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 6 ms 15956 KB Output is correct
6 Correct 6 ms 15956 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 6 ms 15956 KB Output is correct
9 Correct 6 ms 15956 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 6 ms 15956 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 8 ms 15928 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 6 ms 15956 KB Output is correct
6 Correct 6 ms 15956 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 6 ms 15956 KB Output is correct
9 Correct 6 ms 15956 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 6 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 6 ms 15956 KB Output is correct
14 Correct 7 ms 15956 KB Output is correct
15 Correct 7 ms 16000 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 7 ms 15940 KB Output is correct
18 Correct 6 ms 15948 KB Output is correct
19 Correct 7 ms 15956 KB Output is correct
20 Correct 6 ms 16016 KB Output is correct

Subtask #4
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16084 KB Output is correct
2 Correct 8 ms 15928 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 6 ms 15956 KB Output is correct
6 Correct 6 ms 15956 KB Output is correct
7 Correct 6 ms 15956 KB Output is correct
8 Correct 6 ms 15956 KB Output is correct
9 Correct 6 ms 15956 KB Output is correct
10 Correct 6 ms 15956 KB Output is correct
11 Correct 6 ms 15956 KB Output is correct
12 Correct 7 ms 15956 KB Output is correct
13 Correct 6 ms 15956 KB Output is correct
14 Correct 7 ms 15956 KB Output is correct
15 Correct 7 ms 16000 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 7 ms 15940 KB Output is correct
18 Correct 6 ms 15948 KB Output is correct
19 Correct 7 ms 15956 KB Output is correct
20 Correct 6 ms 16016 KB Output is correct
21 Correct 13 ms 16084 KB Output is correct
22 Correct 13 ms 16084 KB Output is correct
23 Correct 14 ms 16084 KB Output is correct
24 Correct 54 ms 16204 KB Output is correct
25 Correct 46 ms 16212 KB Output is correct
26 Correct 48 ms 16212 KB Output is correct
27 Correct 47 ms 16212 KB Output is correct
28 Correct 31 ms 16084 KB Output is correct