Submission #985984

#	Time	Username	Problem	Language	Result	Execution time	Memory
985984		abyyskit	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	256 ms	524288 KiB

kangaroo

#include<iostream>
#include<vector>

using namespace std;


int mod = 1e9 + 7;

void print(vector<int>& as){
	for (auto a: as){
		cout << a << " ";
	}
	cout << "\n";
}

void print(vector<vector<int>>& as){
	for (auto a: as){
		print(a);
	}
}

void print(vector<vector<vector<int>>>& as){
	for (auto a: as){
		print(a);
		cout << "\n";
	}
}

int main(){
	int n, s, e;
	
	cin >> n >> s >> e;
	s--;
	e--;

	vector<vector<vector<int>>> A(n-1, vector<vector<int>>(n, vector<int>(n)));
	vector<vector<vector<int>>> D(n-1, vector<vector<int>>(n, vector<int>(n)));

	for(int i = 0; i < n; ++i){
		for(int j = 0; j < i; ++j){
			A[0][j][i] = 1;
			D[0][i][j] = 1;
		}
	}
	for(int N = 1; N < n-1; ++N){
		for(int j = 1; j < N + 2; ++j){
			// D[N][i][j] = 0;
			int running_sum=0;
			for(int i = 1; i < N + 2; ++i){
				running_sum += A[N-1][i-1][j-1];
				running_sum %= mod;
				if (i < j){
					D[N][i][j] = running_sum;
				}
			}
			// A[N][n-1][j] = 0;
			running_sum = 0;
			for(int i = N; i >= 0; --i){
				running_sum += D[N-1][i][j-1];
				running_sum %= mod;
				if (i < j){
					A[N][i][j] = running_sum;
				}
			}

		}
		for(int j = 0; j < N + 2; ++j){
			for(int i = 0; i < j; ++i){
				if (N%2==0){
					A[N][j][i] = D[N][i][j];
					D[N][j][i] = A[N][i][j];
				}
				else{
					A[N][j][i] = A[N][i][j];
					D[N][j][i] = D[N][i][j];
				}
			}
		}
	}

	//print(A);
	//cout << "\n";
	//print(D);

	cout << (A[n-2][s][e] + D[n-2][s][e])%mod << "\n";

}

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