oj.uz

Submission #1085856

# Submission time Handle Problem Language Result Execution time Memory
1085856 2024-09-08T22:15:57 Z Raiden Skyscraper (JOI16_skyscraper) C++14
15 / 100
 69 ms 136296 KB 
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAX = 105;
int dp[3][MAX][MAX][MAX * 10], n;
int arr[MAX];
int f(int alive_ends, int i,int components, int sm){
	if(alive_ends < 0) return 0;
	if(sm < 0) return 0;
	if(i == n) return alive_ends == 0 && components == 1;
	int &ret = dp[alive_ends][i][components][sm];
	if(~ret) return ret;
	ret = 0;
	sm -= (2 * components - 2 + alive_ends) * (arr[i] - arr[i - 1]);
	ret = (ret + 1LL * (2 * components - 2 + alive_ends) * f(alive_ends, i + 1, components, sm)) % MOD;
	ret = (ret + 1LL * alive_ends * f(alive_ends - 1, i + 1, components, sm)) % MOD;
	ret = (ret + 1LL * (components - 1 + alive_ends) * f(alive_ends, i + 1, components + 1, sm)) % MOD;
	ret = (ret + 1LL * alive_ends * f(alive_ends - 1, i + 1, components + 1, sm)) % MOD;
	ret = (ret + 1LL * (components - 1) * f(alive_ends, i + 1, components - 1, sm)) % MOD;
	return ret;
}
void solve(){
	int k;
	cin >> n >> k;
	memset(dp, -1, sizeof dp);
	for(int i = 0; i < n; i++) cin >> arr[i];
	sort(arr, arr + n);
	if(n == 1){
		cout << 1 << '\n';
		return ;
	}
	cout << (f(2, 1, 1, k) + 2LL * f(1, 1, 1, k)) % MOD << '\n';

}

int32_t main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int t = 1;
	// cin >> t;
	while(t--) solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 136144 KB Output is correct
2 Correct 69 ms 136136 KB Output is correct
3 Correct 62 ms 136272 KB Output is correct
4 Correct 60 ms 136272 KB Output is correct
5 Incorrect 60 ms 136276 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 136272 KB Output is correct
2 Correct 64 ms 136272 KB Output is correct
3 Correct 67 ms 136272 KB Output is correct
4 Correct 67 ms 136276 KB Output is correct
5 Correct 68 ms 136276 KB Output is correct
6 Correct 68 ms 136272 KB Output is correct
7 Correct 67 ms 136268 KB Output is correct
8 Correct 65 ms 136296 KB Output is correct
9 Correct 65 ms 136272 KB Output is correct
10 Correct 69 ms 136160 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 136144 KB Output is correct
2 Correct 69 ms 136136 KB Output is correct
3 Correct 62 ms 136272 KB Output is correct
4 Correct 60 ms 136272 KB Output is correct
5 Incorrect 60 ms 136276 KB Output isn't correct
6 Halted 0 ms 0 KB -