Submission #49342

#	Time	Username	Problem	Language	Result	Execution time	Memory
49342		3zp	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	1832 ms	425624 KiB

kangaroo

#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 = max(0,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[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 (stderr)

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

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 0 / 49