oj.uz

Submission #107398

# Submission time Handle Problem Language Result Execution time Memory
107398 2019-04-24T03:06:01 Z fmrozaqi Skyscraper (JOI16_skyscraper) C++14
5 / 100
 171 ms 181700 KB 
#include <bits/stdc++.h>
#define REP(a, b) for(int a = 0; a < b; a++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define mp make_pair
#define f first
#define s second
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> LL;
typedef vector<int> vi;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//shuffle(permutation.begin(), permutation.end(), rng);
//uniform_int_distribution<int>(l, r)(rng);
const int MAXN = 105;

int n, L;
int A[MAXN];
int DP[MAXN][MAXN][2][2][10 * MAXN];

int rek(int pos, int nyak, int l, int r, int sum) {
	if (sum > L) return 0;
	if (pos == n) {
		if (nyak == 0) return 1;
		return 0;
	}
	int &ret = DP[pos][nyak][l][r][sum];
	if (ret != -1) return ret;
	int sek = 0;
	if (pos) sek = sum + ((l + r + 2 * nyak) * (A[pos] - A[pos - 1]));
	ret = 0;
	
	if (pos == (n - 1)) {
		ret = (ret + rek(pos + 1, nyak, 1, 1, sek)) % MOD;
		return ret;
	}
	
	ret = (ret + rek(pos + 1, nyak, 1, r, sek)) % MOD;
	ret = (ret + rek(pos + 1, nyak, l, 1, sek)) % MOD;
	if (nyak) {
		ll tmp = rek(pos + 1, nyak - 1, 1, r, sek);
		tmp = tmp * nyak % MOD;
		ret = (ret + tmp) % MOD;
		
		tmp = rek(pos + 1, nyak - 1, l, 1, sek);
		tmp = tmp * nyak % MOD;
		ret = (ret + tmp) % MOD;
		
		tmp = rek(pos + 1, nyak, l, r, sek);
		tmp = tmp * nyak % MOD;
		tmp = tmp * 2 % MOD;
		ret = (ret + tmp) % MOD;
		
		if (nyak >= 2) {
			tmp = rek(pos + 1, nyak - 1, l, r, sek);
			tmp = tmp * nyak % MOD;
			tmp = tmp * (nyak - 1) % MOD;
			ret = (ret + tmp) % MOD;
		}
	}
	ret = (ret + rek(pos + 1, nyak + 1, l, r, sek));
	return ret;
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	memset(DP, -1, sizeof DP);
	cin >> n >> L;
	REP(i, n) cin >> A[i];
	sort(A, A + n);
	cout << rek(0, 0, 0, 0, 0) << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 181624 KB Output is correct
2 Correct 154 ms 181624 KB Output is correct
3 Correct 133 ms 181624 KB Output is correct
4 Correct 143 ms 181624 KB Output is correct
5 Correct 152 ms 181456 KB Output is correct
6 Correct 150 ms 181604 KB Output is correct
7 Correct 155 ms 181700 KB Output is correct
8 Correct 171 ms 181624 KB Output is correct
9 Correct 144 ms 181528 KB Output is correct
10 Correct 153 ms 181628 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 181596 KB Output is correct
2 Correct 159 ms 181660 KB Output is correct
3 Correct 153 ms 181624 KB Output is correct
4 Correct 153 ms 181628 KB Output is correct
5 Correct 150 ms 181624 KB Output is correct
6 Correct 136 ms 181624 KB Output is correct
7 Correct 146 ms 181620 KB Output is correct
8 Correct 147 ms 181624 KB Output is correct
9 Incorrect 156 ms 181620 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 181624 KB Output is correct
2 Correct 154 ms 181624 KB Output is correct
3 Correct 133 ms 181624 KB Output is correct
4 Correct 143 ms 181624 KB Output is correct
5 Correct 152 ms 181456 KB Output is correct
6 Correct 150 ms 181604 KB Output is correct
7 Correct 155 ms 181700 KB Output is correct
8 Correct 171 ms 181624 KB Output is correct
9 Correct 144 ms 181528 KB Output is correct
10 Correct 153 ms 181628 KB Output is correct
11 Correct 146 ms 181596 KB Output is correct
12 Correct 159 ms 181660 KB Output is correct
13 Correct 153 ms 181624 KB Output is correct
14 Correct 153 ms 181628 KB Output is correct
15 Correct 150 ms 181624 KB Output is correct
16 Correct 136 ms 181624 KB Output is correct
17 Correct 146 ms 181620 KB Output is correct
18 Correct 147 ms 181624 KB Output is correct
19 Incorrect 156 ms 181620 KB Output isn't correct
20 Halted 0 ms 0 KB -