Submission #1206783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206783		PenguinsAreCute	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++20	5 / 100	9093 ms	328 KiB

festival2

#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;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 27
• Subtask 4: 0 / 14
• Subtask 5: 0 / 36
• Subtask 6: 0 / 13