Submission #966392

#	Time	Username	Problem	Language	Result	Execution time	Memory
966392		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	60 ms	70940 KiB

kangaroo

// In the name of Almighty Allah.
// We're nothing and you're everything.
// Allahu Akbar

#include <bits/stdc++.h>
using namespace std;

#define PI acos(-1.0)
#define FAST_IO ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tii;

const int N = 2e3+5;
const ll mod = 1e9+7;

ll dp[N][N][2][2];

void solve(int tc){
	ll i,j,k,n,m,x,y,s,f,l;
	cin >> n >> s >> f;
	dp[0][0][0][0] = 1;
	for(i=0;i<n;i++){
		for(j=0;j<=i;j++){
			for(k=0;k<2;k++){
				for(l=0;l<2;l++){
					if(i+1 == s){
						if(k == 0){
							dp[i+1][j+1][1][l] += dp[i][j][k][l];
							dp[i+1][j+1][1][l] %= mod;
							if(j>0){ 
								dp[i+1][j][1][l] += dp[i][j][k][l];
								dp[i+1][j][1][l] %= mod;
							}
						}
					}
					else if(i+1 == f){
						if(l == 0){
							dp[i+1][j+1][k][1] += dp[i][j][k][l];
							dp[i+1][j+1][k][1] %= mod;
							if(j>0){
								dp[i+1][j][k][1] += dp[i][j][k][l];
								dp[i+1][j][k][1] %= mod;
							}
						}
					}
					else{
						x = j+1-k-l;
						dp[i+1][j+1][k][l] += x*dp[i][j][k][l];
						dp[i+1][j+1][k][l] %= mod;
						if(j>1){
							dp[i+1][j-1][k][l] += (j-1)*dp[i][j][k][l];
							dp[i+1][j-1][k][l] %= mod;
						}
					}
				}
			}
		}
	}
	// for(i=0;i<=n;i++){
	// 	for(j=0;j<=n;j++){
	// 		cout << "i: " << i << " j: " << j << "\n";
	// 		for(k=0;k<2;k++){
	// 			for(l=0;l<2;l++) cout << dp[i][j][k][l] << " ";
	// 			cout << "\n";	
	// 		}
	// 		cout << "\n";
	// 	}
	// 	cout << "\n";
	// }
	cout << dp[n][1][1][1] << "\n";
}

int main(){
	FAST_IO
	int t = 1;
	//cin >> t;
	for(int tc = 1;tc<=t;tc++){
		solve(tc);
	}
return 0;		
}

Compilation message (stderr)

kangaroo.cpp: In function 'void solve(int)':
kangaroo.cpp:20:13: warning: unused variable 'm' [-Wunused-variable]
   20 |  ll i,j,k,n,m,x,y,s,f,l;
      |             ^
kangaroo.cpp:20:17: warning: unused variable 'y' [-Wunused-variable]
   20 |  ll i,j,k,n,m,x,y,s,f,l;
      |                 ^

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