oj.uz

Submission #49341

# Submission time Handle Problem Language Result Execution time Memory
49341 2018-05-26T09:19:16 Z 3zp Kangaroo (CEOI16_kangaroo) C++14
51 / 100
 2000 ms 197600 KB 
#include<bits/stdc++.h>
using namespace std;
int dp[209][209][209][3];
int prefdp[209][209][209][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++){
        for(int L = 1; L <= n; L++){
            for(int R = 1; R <= n; R++){
                for(int D = 0; D < 2; D++){
                    if(L != R){
                        int nR = R;
                        if (R > L) nR--;
                        if(D == 0){
                            dp[N][L][R][D] += prefdp[N-1][N-1][nR][1-D] - prefdp[N-1][L-1][nR][1-D] + mod;
                            while (dp[N][L][R][D] > mod)  dp[N][L][R][D]-=mod;
                        }
                        else {
                            dp[N][L][R][D] += prefdp[N-1][L-1][nR][1-D];
                            while (dp[N][L][R][D] > mod)  dp[N][L][R][D]-=mod;
                        }
                    }
                    prefdp[N][L][R][D] = prefdp[N][L-1][R][D] + dp[N][L][R][D];
                    if( prefdp[N][L][R][D] > mod)  prefdp[N][L][R][D] -=  mod;
                }
            }
        }
    }
    cout << (dp[n][l][r][0] + dp[n][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 616 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 5 ms 3740 KB Output is correct
4 Correct 10 ms 8384 KB Output is correct
5 Correct 9 ms 8384 KB Output is correct
6 Correct 11 ms 8384 KB Output is correct
7 Correct 10 ms 8384 KB Output is correct
8 Correct 10 ms 8384 KB Output is correct
9 Correct 11 ms 8528 KB Output is correct
10 Correct 11 ms 8528 KB Output is correct
11 Correct 12 ms 8528 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 5 ms 3740 KB Output is correct
4 Correct 10 ms 8384 KB Output is correct
5 Correct 9 ms 8384 KB Output is correct
6 Correct 11 ms 8384 KB Output is correct
7 Correct 10 ms 8384 KB Output is correct
8 Correct 10 ms 8384 KB Output is correct
9 Correct 11 ms 8528 KB Output is correct
10 Correct 11 ms 8528 KB Output is correct
11 Correct 12 ms 8528 KB Output is correct
12 Correct 317 ms 195540 KB Output is correct
13 Correct 401 ms 195540 KB Output is correct
14 Correct 326 ms 195540 KB Output is correct
15 Correct 307 ms 197500 KB Output is correct
16 Correct 319 ms 197500 KB Output is correct
17 Correct 308 ms 197600 KB Output is correct
18 Correct 240 ms 197600 KB Output is correct
19 Correct 309 ms 197600 KB Output is correct
20 Correct 321 ms 197600 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 5 ms 3740 KB Output is correct
4 Correct 10 ms 8384 KB Output is correct
5 Correct 9 ms 8384 KB Output is correct
6 Correct 11 ms 8384 KB Output is correct
7 Correct 10 ms 8384 KB Output is correct
8 Correct 10 ms 8384 KB Output is correct
9 Correct 11 ms 8528 KB Output is correct
10 Correct 11 ms 8528 KB Output is correct
11 Correct 12 ms 8528 KB Output is correct
12 Correct 317 ms 195540 KB Output is correct
13 Correct 401 ms 195540 KB Output is correct
14 Correct 326 ms 195540 KB Output is correct
15 Correct 307 ms 197500 KB Output is correct
16 Correct 319 ms 197500 KB Output is correct
17 Correct 308 ms 197600 KB Output is correct
18 Correct 240 ms 197600 KB Output is correct
19 Correct 309 ms 197600 KB Output is correct
20 Correct 321 ms 197600 KB Output is correct
21 Execution timed out 2090 ms 197600 KB Time limit exceeded
22 Halted 0 ms 0 KB -