oj.uz

Submission #318338

# Submission time Handle Problem Language Result Execution time Memory
318338 2020-11-01T10:10:55 Z HPC Kangaroo (CEOI16_kangaroo) C++17
6 / 100
 1 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e3+5;

int N, S, T;
int dp[MAXN][MAXN];

int main(){
    cin >> N >> S >> T;
    if(S > T){
        swap(S,T);
    }
    if(N == 1){
        cout << "1\n";
        return 0;
    }
    dp[0][0] = 1;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(i == S || i == T){
                dp[i][j] = dp[i-1][j]+dp[i-1][j-1];
            }else if(i > T){
                dp[i][j] = (j-2)*dp[i-1][j-1]+j*dp[i-1][j+1];
            }else if(i > S){
                dp[i][j] = (j-1)*dp[i-1][j-1]+j*dp[i-1][j+1];
            }else{
                dp[i][j] = j*dp[i-1][j-1]+j*dp[i-1][j+1];
            }/*
            dp[i][j][0] = j*dp[i-1][j-1][0]+j*dp[i-1][j+1][0];
            dp[i][j][1] = (j-1)*dp[i-1][j-1][1]+j*dp[i-1][j+1][1]+2*dp[i-1][j][0]+2*dp[i-1][j-1][0];
            dp[i][j][2] = (j-2)*dp[i-1][j-1][2]+j*dp[i-1][j+1][2]+dp[i-1][j][1]+dp[i-1][j-1][1];*/
        }
    }
    cout << dp[N][1] << '\n';
  	return 0;
}

/*
https://oj.uz/problem/view/CEOI16_kangaroo
A[i]>A[i-1] 
2 1 5 3 4
(N-2)!
*/

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 49.0

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