제출 #570873

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

kangaroo

#include <bits/stdc++.h>

using namespace std;
#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int, int>             pii;
typedef pair<pii, int>              piii;
typedef pair<long long, long long> pll;
typedef pair<pll, long long>        plll;
typedef vector<int>                vi;
typedef vector<vector<int>>        vvi;
typedef vector<long long>          vl;
typedef vector<vector<long long>>  vll;
typedef vector<pii>                vpii;
typedef vector<piii>               vpiii;
typedef vector<pll>                vpll;
typedef vector<plll>               vplll;
typedef vector<vector<plll>>       vvplll;
typedef vector<vector<pll>>        vvpll;
typedef vector<vector<piii>>       vvpiii;
typedef vector<vector<pii>>        vvpii;
#define pb push_back
#define mp make_pair
#define data data_
#define endl "\n"
#define isOn(S, j) (S & (1ll << (j)))
#define setBit(S, j) (S |= (1ll << (j)))
#define clearBit(S, j) (S &= ~(1ll << (j)))
#define toggleBit(S, j) (S ^= (1ll << (j)))
#define bzero(b,len) (memset((b), '\0', (len)), (void) 0)

const long long MOD = 1000000007;
int main(){
	optimizar_io;
	int N, cs, cf;
	cin >> N >> cs >> cf;
	long long dp[N+2][N+2]; //dp[i][j] number of ways to create j chunks with the i first elements fulfilling the 
	                  //alternating conditions. Each chunk has an odd number of elements and starts increasing
										//and finishes decreasing, except maybe the first and last one, which can start and finish
										//in either direction
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	bool startPlaced = false, endPlaced = false;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= i; j++){
			if (i == cs){//It must be placed in the first position
				startPlaced = true;
				dp[i][j] = dp[i-1][j-1];//place it alone
				if ((j != 1) || (!endPlaced)) { //Tie it to a chunk
					dp[i][j] += dp[i-1][j];//Tie it to a chunk
					dp[i][j] %= MOD;
				}
			} else if (i == cf){//It must be placed in the last position
				endPlaced = true;
				dp[i][j] = dp[i-1][j-1];//place it alone
				if ((j != 1) || (!startPlaced)){ //Tie it to a chunk
					dp[i][j] += dp[i-1][j];
					dp[i][j] %= MOD;
				}
			} else { //It must be placed between two existing chunks or placed alone
				dp[i][j] = 0;
				dp[i][j] += dp[i-1][j+1] * (j);//Unir dos exisentes de los j + 1 (j opciones)
				dp[i][j] %= MOD;
				int options = j - 2;
				if (!startPlaced) options++;
				if (!endPlaced) options++;
				if (options >= 1){
					dp[i][j] += dp[i-1][j-1] * (options);//Ponerlo entre cualquiera de los j - 1 (j - 2 opciones) o al principio o al final
					dp[i][j] %= MOD;
				}
			}	
		}
	}
	/*for (int i = 1; i <= N; i++){
		for (int j = 0; j <= N; j++){
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}*/
	cout << dp[N][1] << endl;

	return 0;
}

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