Submission #1285744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285744		Jawad_Akbar_JJ	캥거루 (CEOI16_kangaroo)	C++17	36 / 100	3 ms	1040 KiB

kangaroo

#include <iostream>

using namespace std;
const int N = 45, mod = 1e9 + 7;
int A[N][N][N], D[N][N][N];

void precompute(){
	A[2][1][2] = D[2][2][1] = 1;

	for (int i=3;i<N;i++){
		// cout<<i<<endl;
		for (int j=1;j<i;j++){
			for (int k=j+1;k<=i;k++){
				for (int l=j;l<i;l++)
					A[i][j][k] = (A[i][j][k] + D[i-1][l][k-1]) % mod;
			}
		}

		for (int j=1;j<=i;j++){
			for (int k=j+1;k<=i;k++){
				for (int l=1;l<j;l++)
					D[i][j][k] = (D[i][j][k] + A[i-1][l][k-1]) % mod;
			}
		}

		for (int j=1;j<=i;j++){
			for (int k=j+1;k<=i;k++){
				if (i % 2 == 1)
					A[i][k][j] = A[i][j][k], D[i][k][j] = D[i][j][k];
				else
					A[i][k][j] = D[i][j][k], D[i][k][j] = A[i][j][k];
				// if (i == 4)
					// cout<<j<<" "<<k<<" "<<A[i][j][k]<<" "<<D[i][j][k]<<'\n';
			}
		}
	}
}

int main(){
	precompute();
	int n, s, t;
	cin>>n>>s>>t;

	if (s > t)
		swap(s, t);
	cout<<(A[n][s][t] + D[n][s][t]) % mod<<'\n';
}

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