답안 #98296 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98296	2019-02-21T23:19:35 Z	qkxwsm	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	1533 ms	525312 KB

skyscraper

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

random_device(rd);
mt19937 rng(rd());
const long long FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();

struct custom_hash
{
	template<class T>
	unsigned long long operator()(T v) const
	{
		unsigned long long x = v;
		x += FIXED_RANDOM;
		// x += 11400714819323198485ull;
		// x = (x ^ (x >> 30)) * 13787848793156543929ull;
		x = (x ^ (x >> 27)) * 10723151780598845931ull;
		return x ^ (x >> 31);
	}
};

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U> using hash_table = gp_hash_table<T, U, custom_hash>;

template<class T>
T randomize(T mod)
{
	return (uniform_int_distribution<T>(0, mod - 1))(rng);
}
template<class T>
void readi(T &x)
{
	x = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		x = -x;
	}
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int buf[20], n = 0;
	while(output)
	{
		buf[n] = ((output % 10));
		output /= 10;
		n++;
	}
	for (n--; n >= 0; n--)
	{
		putchar(buf[n] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long expo(long long a, long long e, long long mod)
{
	return ((e == 0) ? 1 : ((expo(a * a % mod, e >> 1, mod)) * ((e & 1) ? a : 1) % mod));
}
template<class T, class U>
void nmod(T &x, U mod)
{
	if (x >= mod) x -= mod;
}
template<class T>
T gcd(T a, T b)
{
	return (b ? gcd(b, a % b) : a);
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define DBG(x) cerr << #x << " = " << (x) << endl
#define SZ(x) ((int) ((x).size()))
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define ALL(x) (x).begin(), (x).end()

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-9;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 113

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<pdd> vpd;

int N, L;
int arr[MAXN];
hash_table<int, ll> dp[MAXN][2][2][MAXN];
ll ans;

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	// cout << fixed << setprecision(10);
	// cerr << fixed << setprecision(10);
	// if (fopen("file.in", "r"))
	// {
	// 	freopen ("file.in", "r", stdin);
	// 	freopen ("file.out", "w", stdout);
	// }
	cin >> N >> L;
	if (N == 1)
	{
		cout << "1\n";
		return 0;
	}
	FOR(i, 0, N)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	if (arr[N - 1] - arr[0] > L)
	{
		cout << "0\n";
		return 0;
	}
	FOR(i, 0, L + 1)
	{
		dp[N - 1][1][1][1][i] = 1;
	}
	int hello = 0;
	FORD(i, N, 1)
	{
		FOR(j, 0, 2)
		{
			FOR(k, 0, 2)
			{
				FOR(m, 1, N + 1)
				{
					for (auto x : dp[i][j][k][m])
					{
						hello++; if (hello >= 10000000) return 0;
						int n = x.fi;
						ll val = x.se % INF; if (val == 0) continue;
						if (j)
						{
							//latch onto the left!
							dp[i - 1][0][k][m][n - arr[i]] += val;
							//new guy on the left!
							dp[i - 1][0][k][m - 1][n + arr[i]] += val;
						}
						if (k)
						{
							//latch onto the right!
							dp[i - 1][j][0][m][n - arr[i]] += val;
							//new guy on the right!
							dp[i - 1][j][0][m - 1][n + arr[i]] += val;
						}
						//new cc by itself
						dp[i - 1][j][k][m - 1][n + 2 * arr[i]] += val * (m - j - k);
						//join two cc
						dp[i - 1][j][k][m + 1][n - 2 * arr[i]] += val * (m);
						//latch on left, right
						dp[i - 1][j][k][m][n] += val * (2 * m - j - k);
					}
				}
			}
		}
	}
	ans += dp[0][0][0][1][-2 * arr[0]];
	ans += dp[0][1][0][1][-arr[0]];
	ans += dp[0][0][1][1][-arr[0]];
	ans %= INF;
	cout << ans << '\n';
	//when we place a # down, we can either say: ok new left spot open! ok new right spot open! ok new nothing open!
	//dp of:
	//total sum,
	// cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
	return 0;
}
/* READ READ READ
* int overflow, maxn too small, special cases (n=1?, two distinct?), cin.tie() interactive
* reread the problem, try small cases
* note down possible sources of error as you go
* do smth instead of nothing
*/

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	16000 KB	Output is correct
2	Correct	22 ms	16000 KB	Output is correct
3	Correct	19 ms	16000 KB	Output is correct
4	Correct	28 ms	16768 KB	Output is correct
5	Correct	62 ms	33968 KB	Output is correct
6	Correct	63 ms	34968 KB	Output is correct
7	Correct	20 ms	16012 KB	Output is correct
8	Correct	22 ms	16896 KB	Output is correct
9	Correct	69 ms	35400 KB	Output is correct
10	Correct	27 ms	17528 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	17920 KB	Output is correct
2	Correct	51 ms	27132 KB	Output is correct
3	Correct	38 ms	18776 KB	Output is correct
4	Correct	46 ms	26716 KB	Output is correct
5	Correct	52 ms	28408 KB	Output is correct
6	Correct	34 ms	22264 KB	Output is correct
7	Correct	29 ms	18936 KB	Output is correct
8	Correct	28 ms	18432 KB	Output is correct
9	Correct	35 ms	19456 KB	Output is correct
10	Correct	44 ms	25464 KB	Output is correct

Subtask #3
0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	16000 KB	Output is correct
2	Correct	22 ms	16000 KB	Output is correct
3	Correct	19 ms	16000 KB	Output is correct
4	Correct	28 ms	16768 KB	Output is correct
5	Correct	62 ms	33968 KB	Output is correct
6	Correct	63 ms	34968 KB	Output is correct
7	Correct	20 ms	16012 KB	Output is correct
8	Correct	22 ms	16896 KB	Output is correct
9	Correct	69 ms	35400 KB	Output is correct
10	Correct	27 ms	17528 KB	Output is correct
11	Correct	24 ms	17920 KB	Output is correct
12	Correct	51 ms	27132 KB	Output is correct
13	Correct	38 ms	18776 KB	Output is correct
14	Correct	46 ms	26716 KB	Output is correct
15	Correct	52 ms	28408 KB	Output is correct
16	Correct	34 ms	22264 KB	Output is correct
17	Correct	29 ms	18936 KB	Output is correct
18	Correct	28 ms	18432 KB	Output is correct
19	Correct	35 ms	19456 KB	Output is correct
20	Correct	44 ms	25464 KB	Output is correct
21	Correct	297 ms	102548 KB	Output is correct
22	Runtime error	1533 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
23	Halted	0 ms	0 KB	-

답안 #98296

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 15.0 / 15.0

Subtask #3 0 / 80.0

Subtask #1
5.0 / 5.0

Subtask #2
15.0 / 15.0

Subtask #3
0 / 80.0