Submission #343259

#	Time	Username	Problem	Language	Result	Execution time	Memory
343259		S2speed	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	273 ms	194796 KiB

skyscraper

#include<bits/stdc++.h>
#include<fstream>
 
using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define gcd __gcd 
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
struct piii {
	int first , second , third;
};

const ll MAX_N = 1 << 14 , md = 1e9 + 7;
 
ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n;
		}
		n *= n;
		k /= 2;
	}
	return res;
}

ll cnt[MAX_N][101][15];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	int n , l;
	ll ans = 0;
	cin>>n>>l;
	vector<ll> a(n);
	if(n <= 8){
		for(int i = 0 ; i < n ; i++){
			cin>>a[i];
		}
		int sum = 0;
		sort(a.begin() , a.end());
		for(int i = 1 ; i < n ; i++){
			sum += abs(a[i] - a[i - 1]);
		}
		ans += (sum <= l);
		while(next_permutation(a.begin() , a.end())){
			sum = 0;
			for(int i = 1 ; i < n ; i++){
				sum += abs(a[i] - a[i - 1]);
			}
			ans += (sum <= l);
		}
		cout<<ans<<'\n';
		return 0;
	}
	if(n > 14 || l > 100) return 0;
	for(int i = 0 ; i < n ; i++){
		cin>>a[i];
	}
	int h = 1 << n;
	for(int i = 0 ; i < h ; i++){
		for(int j = 0 ; j < n ; j++){
			cnt[i][0][j] = (__builtin_popcount(i) < 2);
			for(int q = 1 ; q < 101 ; q++){
				cnt[i][q][j] = 0;
			}
		}
	}
	for(int i = 0 ; i < h ; i++){
		if(__builtin_popcount(i) < 2) continue;
		int o = 1;
		for(int j = 0 ; j < n ; j++){
			if(i & o){
				int p = i ^ o , k = 1;
				for(int q = 0 ; q < n ; q++){
					if(k & p){
						for(int y = 0 ; y < 101 ; y++){
							int d = y + abs(a[j] - a[q]);
							if(d > l) break;
							cnt[i][d][j] += cnt[p][y][q];
						}
					}
					k *= 2;
				}
			}
			o *= 2;
		}
	}
	for(int i = 0 ; i <= l ; i++){
		for(int j = 0 ; j < n ; j++){
			ans += cnt[h - 1][i][j];
		}
	}
	cout<<ans % md<<'\n';
	return 0;
}

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