Submission #1206783

#TimeUsernameProblemLanguageResultExecution timeMemory
1206783PenguinsAreCuteFestivals in JOI Kingdom 2 (JOI23_festival2)C++20
5 / 100
9093 ms328 KiB
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> a, vector<int> b) {
	int n = a.size();
	for(int i=0;i<n;i++)
		if(a[i]>b[i])
			return 0;
	int dp[n];
	for(int i=n;i--;) {
		dp[i] = 0;
		for(int j=i+1;j<n;j++)
			if(a[j] > b[i])
				dp[i] = max(dp[i], dp[j]);
		dp[i]++;
	}
	int tim = 0, cnt = 0;
	while(1) {
		auto it = lower_bound(a.begin(),a.end(),tim);
		if(it == a.end())
			break;
		tim = b[it-a.begin()];
		cnt++;
	}
	return (cnt < *max_element(dp,dp+n));
}
int main() {
	int n, p, ans = 0;
	cin >> n >> p;
	for(int i=0;i<(1<<(2*n));i++)
		if(__builtin_popcount(i) == n) {
			vector<int> a, b;
			for(int j=0;j<2*n;j++)
				(i&(1<<j)?b:a).push_back(j);
			do
				ans += solve(a, b);
			while(next_permutation(b.begin(),b.end()));
		}
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...