Submission #685022

#	Time	Username	Problem	Language	Result	Execution time	Memory
685022		NeroZein	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	21 ms	352 KiB

kangaroo

/*
 *    author: NeroZein
 *    created: 23.01.2023 08:16:46
*/
#include <bits/stdc++.h>
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int md = 1e9+7;

inline int add(int a, int b){
	a += b;
	if(a >= md){
		a -= md;
	}
	return a;
}

inline int mul(int a, int b){
	return (int)((long long) a * b % md);
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, cs, cf;
	cin >> n >> cs >> cf;
	vector<int> dp(n);
	dp[1] = 1; 
	for (int i = 2; i <= n; ++i){
		vector<int> pd(n); 
		for (int j = 1; j < n; ++j){
			//endpoint either 
			if(i == cs || i == cf){
				//alone or to the left or right to existing set
				pd[j] = add(dp[j-1], dp[j]);
			}
			else{
				//merge two sets or start a new one
				pd[j] = add(mul(j, dp[j+1]), mul(j - (i > cs) - (i > cf), dp[j-1]));
			}
		}
		swap(dp, pd);
	}
	cout << dp[1]; 
}

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