oj.uz

Submission #49345

# Submission time Handle Problem Language Result Execution time Memory
49345 2018-05-26T09:33:05 Z 3zp Kangaroo (CEOI16_kangaroo) C++14
6 / 100
 3 ms 1148 KB 
#include<bits/stdc++.h>
using namespace std;
int dp[3][2009][2009][3];
int prefdp[3][2009][2009][3];
int mod = 1e9+ 7;
main(){
    int n,l,r;
    cin >> n >> l >> r;
    dp[1][1][1][1] = 1;
    dp[1][1][1][0] = 1;
    prefdp[1][1][1][1] = 1;
    prefdp[1][1][1][0] = 1;
    for(int N = 2; N <= n; N++){
        int n0 = N % 2, n1 = 1 - n0;
        for(int L = 1; L <= n; L++){
            for(int R = max(1 ,r - (n- N)); R <= r; R++){
                for(int D = 0; D < 2; D++){

                    if(L != R){
                        int nR = R;
                        if (R > L) nR--;
                        if(D == 0){
                            dp[n0][L][R][D] += prefdp[n1][N-1][nR][1-D] - prefdp[n1][L-1][nR][1-D] + mod;
                            while (dp[n0][L][R][D] >= mod)  dp[n0][L][R][D]-=mod;
                        }
                        else {
                            dp[n0][L][R][D] += prefdp[n1][L-1][nR][1-D];
                            while (dp[n0][L][R][D] >= mod)  dp[n0][L][R][D]-=mod;
                        }
                    }
                    prefdp[n0][L][R][D] = prefdp[n0][L-1][R][D] + dp[n0][L][R][D];
                    if( prefdp[n0][L][R][D] >= mod)  prefdp[n0][L][R][D] -=  mod;
                }

            }
        }
    }
    cout << (dp[n%2][l][r][0] + dp[n%2][l][r][1]) % mod << endl;
}

Compilation message

kangaroo.cpp:6:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 944 KB Output is correct
4 Incorrect 3 ms 1148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 944 KB Output is correct
4 Incorrect 3 ms 1148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 944 KB Output is correct
4 Incorrect 3 ms 1148 KB Output isn't correct
5 Halted 0 ms 0 KB -