제출 #1005187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1005187		Muaath_5	캥거루 (CEOI16_kangaroo)	C++17	6 / 100	14 ms	36444 KiB

kangaroo

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 2007;

int n, cs, cf;
int frq[N] = {};
int ff[N][N] = {};

int gg[N][N];

deque<int> lvl[N];

int main()
{
	//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> cs >> cf;
	if (n <= 10) {
		vector<int> p(n);
		iota(p.begin(), p.end(), 1);
		int sol = 0;
		do {
			int f = p[0] < p[1];
			for (int i = 1; i < n; i++) {
				if (f && p[i-1] > p[i]) {f = -1; break;}
				if (!f && p[i-1] < p[i]) {f = -1; break;}
				f = !f;
			}
			if (f != -1) {
				//for (int i:p)cerr<<i;cerr<<endl;
				sol++;	
				frq[p[0]]++;
				ff[p[0]][p[n-1]]++;
			}
		} while (next_permutation(p.begin(), p.end()));
		cout << ff[cs][cf] << endl;
		#ifndef MUAATH_5
		return 0;
		#endif
	}
		
	// for (int i = 1; i <= n; i++) {
		// for (int j = 1; j <= n; j++)
			// cout << ff[i][j] << ' ';
		// cout << endl;
	// }
	
	
	lvl[3] = {0, 1, 0};
	lvl[4] = {0, 0, 1, 1};
	int cursize = 5;
	while (cursize <= n) {
		lvl[cursize] = lvl[cursize-1];
		if (cursize % 2 == 1) {
			lvl[cursize].push_back(0);
			for (int i = cursize-2; i > 0; i--)
				lvl[cursize][i] += lvl[cursize][i+1];
		} else {
			lvl[cursize].push_front(0);
			for (int i = 3; i < cursize; i++)
				lvl[cursize][i] += lvl[cursize][i-1];
		}
		cursize++;
	}
	
	memset(gg, -1, sizeof gg);
	for (int i = 1; i <= n; i++) {
		gg[i][1] = gg[1][i] = gg[n-1+1][n-i+1] = gg[n-i+1][n-1+1] = lvl[n][i-1];
	}

	if (n&1) {
		for (int i = 2; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) gg[i][i] = 0;
				if (gg[i][j] == -1) {
					gg[i][j] = gg[j][i] = gg[n-j+1][n-i+1] = gg[n-i+1][n-j+1]
					= gg[i-1][j-1];// - (j > n/2 ? 2*(i-2) : 0);
				}
			}
		}
	} else {
		for (int i = 2; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) gg[i][i] = 0;
				if (gg[i][j] == -1) {
					gg[i][j] = gg[j][i] = gg[n-j+1][n-i+1] = gg[n-i+1][n-j+1]
					= gg[i-1][j] + lvl[n-i+1][j-i+1];// - (j > n/2 ? 2*(i-2) : 0);
				}
			}
		}
	}
	
	
	cout << gg[cs][cf];
	assert(gg[cs][cf] == ff[cs][cf]);
	// cout << endl << endl;
	// for (int i = 1; i <= n; i++) {
		// for (int j = 1; j <= n; j++) {
			// //cout << gg[i][j] << ' ';
			// cout << flush;
			// //assert(gg[i][j] == ff[i][j]);
		// }
		// cout << endl;
	// }
}

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