oj.uz

Submission #966421

# Submission time Handle Problem Language Result Execution time Memory
966421 2024-04-19T20:29:58 Z vjudge1 Kangaroo (CEOI16_kangaroo) C++17
100 / 100
 6 ms 656 KB 
// 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[2][N];

void solve(int tc){
	ll i,j,k,n,m,x,y,s,f,l;
	cin >> n >> s >> f;
	for(i=1;i<=n;i++){
		for(j=1;j<=i;j++){
			if(i == 1 && j == 1) dp[i&1][j] = 1;
			else if(i == s || i == f){
				dp[i&1][j] = dp[(i-1)&1][j-1] + dp[(i-1)&1][j];
			}
			else{
				x = j;
				if(i>s) x--;
				if(i>f) x--;
				dp[i&1][j] = dp[(i-1)&1][j+1]*j + dp[(i-1)&1][j-1]*x;
			}
			dp[i&1][j] %= mod;
		}
	}
	cout << dp[n&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

kangaroo.cpp: In function 'void solve(int)':
kangaroo.cpp:20:9: warning: unused variable 'k' [-Wunused-variable]
   20 |  ll i,j,k,n,m,x,y,s,f,l;
      |         ^
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;
      |                 ^
kangaroo.cpp:20:23: warning: unused variable 'l' [-Wunused-variable]
   20 |  ll i,j,k,n,m,x,y,s,f,l;
      |                       ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 500 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 500 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 6 ms 348 KB Output is correct
25 Correct 5 ms 476 KB Output is correct
26 Correct 5 ms 348 KB Output is correct
27 Correct 5 ms 348 KB Output is correct
28 Correct 4 ms 656 KB Output is correct