oj.uz

Submission #164685

# Submission time Handle Problem Language Result Execution time Memory
164685 2019-11-22T15:50:11 Z ttnhuy313 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 2000 ms 173944 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;
}

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;
}

Compilation message

skyscraper.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 173908 KB Output is correct
2 Correct 157 ms 173732 KB Output is correct
3 Correct 193 ms 173788 KB Output is correct
4 Correct 152 ms 173816 KB Output is correct
5 Correct 152 ms 173816 KB Output is correct
6 Correct 158 ms 173816 KB Output is correct
7 Correct 158 ms 173772 KB Output is correct
8 Correct 154 ms 173788 KB Output is correct
9 Correct 158 ms 173772 KB Output is correct
10 Correct 152 ms 173816 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 173780 KB Output is correct
2 Correct 162 ms 173752 KB Output is correct
3 Correct 155 ms 173816 KB Output is correct
4 Correct 161 ms 173816 KB Output is correct
5 Correct 160 ms 173836 KB Output is correct
6 Correct 162 ms 173944 KB Output is correct
7 Correct 159 ms 173824 KB Output is correct
8 Correct 160 ms 173816 KB Output is correct
9 Correct 158 ms 173836 KB Output is correct
10 Correct 161 ms 173848 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 173908 KB Output is correct
2 Correct 157 ms 173732 KB Output is correct
3 Correct 193 ms 173788 KB Output is correct
4 Correct 152 ms 173816 KB Output is correct
5 Correct 152 ms 173816 KB Output is correct
6 Correct 158 ms 173816 KB Output is correct
7 Correct 158 ms 173772 KB Output is correct
8 Correct 154 ms 173788 KB Output is correct
9 Correct 158 ms 173772 KB Output is correct
10 Correct 152 ms 173816 KB Output is correct
11 Correct 155 ms 173780 KB Output is correct
12 Correct 162 ms 173752 KB Output is correct
13 Correct 155 ms 173816 KB Output is correct
14 Correct 161 ms 173816 KB Output is correct
15 Correct 160 ms 173836 KB Output is correct
16 Correct 162 ms 173944 KB Output is correct
17 Correct 159 ms 173824 KB Output is correct
18 Correct 160 ms 173816 KB Output is correct
19 Correct 158 ms 173836 KB Output is correct
20 Correct 161 ms 173848 KB Output is correct
21 Correct 288 ms 173816 KB Output is correct
22 Execution timed out 2080 ms 173816 KB Time limit exceeded
23 Halted 0 ms 0 KB -