oj.uz

Submission #164687

# Submission time Handle Problem Language Result Execution time Memory
164687 2019-11-22T15:55:48 Z ttnhuy313 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 2000 ms 173928 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 105, L = 1005, MOD = 1e9 + 7;
int dp[N][L][2][N][2], a[N], n, maxCost;

void add(int &a, int b) {
	a = (a + b) % MOD;
	return;
}

int calc(int pos, int curCost, int l, int k, int r) {
	int nxtCost = curCost;
	if (pos > 1)
		nxtCost += (l + (k << 1) + r) * (a[pos] - a[pos - 1]);
	if (nxtCost > maxCost) return 0;
	if (pos == n)
		return (k == 0 ? 1 : 0);
	if (~dp[pos][curCost][l][k][r]) return dp[pos][curCost][l][k][r];
	int ret = 0;
	add(ret, calc(pos + 1, nxtCost, 1, k, r));
	add(ret, 1LL * calc(pos + 1, nxtCost, 1, k - 1, r) * k % MOD);
	add(ret, calc(pos + 1, nxtCost, l, k, 1));
	add(ret, 1LL * calc(pos + 1, nxtCost, l, k - 1, 1) * k % MOD);
	add(ret, calc(pos + 1, nxtCost, l, k + 1, r));
	add(ret, 1LL * calc(pos + 1, nxtCost, l, k - 1, r) * k * (k - 1) % MOD);
	add(ret, 1LL * calc(pos + 1, nxtCost, l, k, r) * k * 2 % MOD);
	ret %= MOD;
	return dp[pos][curCost][l][k][r] = ret;
}

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

	memset(dp, -1, sizeof dp);
	cin >> n >> maxCost;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	sort(a + 1, a + 1 + n);
	cout << calc(1, 0, 0, 0, 0) << endl;

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 173928 KB Output is correct
2 Correct 153 ms 173816 KB Output is correct
3 Correct 153 ms 173788 KB Output is correct
4 Correct 153 ms 173728 KB Output is correct
5 Correct 156 ms 173840 KB Output is correct
6 Correct 152 ms 173764 KB Output is correct
7 Correct 152 ms 173816 KB Output is correct
8 Correct 165 ms 173896 KB Output is correct
9 Correct 159 ms 173820 KB Output is correct
10 Correct 154 ms 173788 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 173804 KB Output is correct
2 Correct 162 ms 173812 KB Output is correct
3 Correct 165 ms 173900 KB Output is correct
4 Correct 162 ms 173816 KB Output is correct
5 Correct 162 ms 173816 KB Output is correct
6 Correct 159 ms 173832 KB Output is correct
7 Correct 174 ms 173912 KB Output is correct
8 Correct 161 ms 173816 KB Output is correct
9 Correct 154 ms 173816 KB Output is correct
10 Correct 159 ms 173900 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 173928 KB Output is correct
2 Correct 153 ms 173816 KB Output is correct
3 Correct 153 ms 173788 KB Output is correct
4 Correct 153 ms 173728 KB Output is correct
5 Correct 156 ms 173840 KB Output is correct
6 Correct 152 ms 173764 KB Output is correct
7 Correct 152 ms 173816 KB Output is correct
8 Correct 165 ms 173896 KB Output is correct
9 Correct 159 ms 173820 KB Output is correct
10 Correct 154 ms 173788 KB Output is correct
11 Correct 155 ms 173804 KB Output is correct
12 Correct 162 ms 173812 KB Output is correct
13 Correct 165 ms 173900 KB Output is correct
14 Correct 162 ms 173816 KB Output is correct
15 Correct 162 ms 173816 KB Output is correct
16 Correct 159 ms 173832 KB Output is correct
17 Correct 174 ms 173912 KB Output is correct
18 Correct 161 ms 173816 KB Output is correct
19 Correct 154 ms 173816 KB Output is correct
20 Correct 159 ms 173900 KB Output is correct
21 Correct 281 ms 173832 KB Output is correct
22 Execution timed out 2062 ms 173840 KB Time limit exceeded
23 Halted 0 ms 0 KB -