oj.uz

Submission #343719

# Submission time Handle Problem Language Result Execution time Memory
343719 2021-01-04T12:18:06 Z Millad Skyscraper (JOI16_skyscraper) C++14
20 / 100
 739 ms 483680 KB 
// In the name of god
#include <bits/stdc++.h>
 
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define Sort(x) sort(all(x))
#define debug(x) cerr << #x << " : " << x << "\n"
#define use_file freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef string str;
 
const ll maxn = 1e5 + 6, MsK = 2e4, inf = 1e18, mod = 1e9 + 7;
ll n, L, a[maxn], dp[MsK][15][105], pw2[30], b[maxn];
map<pll, ll> mp;
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	pw2[0] = 1;
	for(ll i = 1; i < 16; i ++)pw2[i] = pw2[i - 1] * 2ll;
	cin >> n >> L;
	if(n == 1)return cout << 1 << endl, 0;
	for(ll i = 0; i < n; i ++)cin >> a[i];
	if(n < 9){
		for(ll i = 0; i < n; i ++)b[i] = i;
		ll ans = 0;
		while(true){
			ll dif = 0;
			for(ll i = 1; i < n; i ++)dif += abs(a[b[i]] - a[b[i - 1]]);
			if(dif <= L)ans ++;
			if(next_permutation(b, b + n))ans = ans; 
			else break;
		}
		return cout << ans << "\n", 0;
	}
	ll z = 1;
	for(ll i = 0; i < n; i ++)z *= 2;
	for(ll msk = 1; msk < z; msk ++){
		if(__builtin_popcount(msk) == 1)continue;
		if(__builtin_popcount(msk) == 2){
			vector <ll> V;
			for(ll i = 0; i < n; i ++){
				if(pw2[i] & msk)V.pb(i);
			}
			ll dif = abs(a[V[0]] - a[V[1]]);
			if(dif > L)continue;
			dp[msk][V[0]][dif] = 1;
			dp[msk][V[1]][dif] = 1;
			continue;
		}
		for(ll i = 0; i < n; i ++){
			if((pw2[i] & msk) == 0)continue;
			for(ll j = 0; j < n; j ++){
				if((pw2[j] & msk) == 0)continue;
				if(i == j)continue;
				for(ll l = 0; l <= L; l ++){
					if((l + abs(a[i] - a[j])) > L)continue;
					(dp[msk][i][l + abs(a[i] - a[j])] += dp[(msk ^ pw2[i])][j][l]) %= mod;
				}
			}
		}
	}
	ll ans = 0;
	for(ll i = 0; i < n; i ++){
		for(ll l = 0; l <= L; l ++)(ans += dp[z - 1][i][l]) %= mod;
	}
	cout << ans << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 46956 KB Output is correct
2 Correct 402 ms 196124 KB Output is correct
3 Correct 305 ms 194972 KB Output is correct
4 Correct 369 ms 196332 KB Output is correct
5 Correct 436 ms 196204 KB Output is correct
6 Correct 373 ms 196204 KB Output is correct
7 Correct 264 ms 194172 KB Output is correct
8 Correct 331 ms 194892 KB Output is correct
9 Correct 367 ms 196000 KB Output is correct
10 Correct 373 ms 195944 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 65 ms 46956 KB Output is correct
12 Correct 402 ms 196124 KB Output is correct
13 Correct 305 ms 194972 KB Output is correct
14 Correct 369 ms 196332 KB Output is correct
15 Correct 436 ms 196204 KB Output is correct
16 Correct 373 ms 196204 KB Output is correct
17 Correct 264 ms 194172 KB Output is correct
18 Correct 331 ms 194892 KB Output is correct
19 Correct 367 ms 196000 KB Output is correct
20 Correct 373 ms 195944 KB Output is correct
21 Runtime error 739 ms 483680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -