Submission #49344

#	Time	Username	Problem	Language	Result	Execution time	Memory
49344		3zp	Kangaroo (CEOI16_kangaroo)	C++14	6 / 100	3 ms	1152 KiB

kangaroo

#include<bits/stdc++.h>
using namespace std;
int dp[2][2009][2009][3];
int prefdp[2][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(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[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 (stderr)

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

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