Submission #85604

#	Time	Username	Problem	Language	Result	Execution time	Memory
85604		MatheusLealV	Skyscraper (JOI16_skyscraper)	C++17	0 / 100	722 ms	764 KiB

skyscraper

#include <bits/stdc++.h>
#define N 110
using namespace std;

int n, L, v[N];

int solve(int i, int free, int k, int l, int r)
{
	if(free < 0) return 0;

	if(i == n)
	{
		if( (!l and !r) or free != 0) return 0;

		if(!l or !r) return (k + v[i] <= L);

		return (k + 2*v[i] <= L);
	}

	int ini1 = solve(i + 1, free, k - v[i], 1, r); // Nao junta com ninguem

	int ini2 = solve(i + 1, free - 1, k + v[i], 1, r); // Junta com 1 "free"

	int fim1 = solve(i + 1, free, k - v[i], l, 1);

	int fim2 = solve(i + 1, free - 1, k + v[i], l, 1);

	int nova = solve(i + 1, free + 1, k - 2*v[i], l, r); // Cria nova componente

	int byl = solve(i + 1, free, k, l, r)*(free + r);

	int byr = solve(i + 1, free, k, l, r)*(free + l);

	int merge = solve(i + 1, free - 1, k + 2*v[i], l, r)*(free - 1 + l + r);

	int ans = nova + byl + byr + merge;

	if(!l) ans += ini1 + ini2;

	if(!r) ans += fim1 + fim2;

	return ans;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>L;

	for(int i = 1; i <= n; i++) cin>>v[i];

	sort(v + 1, v + n + 1);

	cout<<solve(1, 0, 0, 0, 0)<<"\n";
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 80