oj.uz

Submission #1086345

# Submission time Handle Problem Language Result Execution time Memory
1086345 2024-09-10T09:40:19 Z Raiden Skyscraper (JOI16_skyscraper) C++14
0 / 100
 72 ms 136496 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 - alive_ends) * (arr[i] - arr[i - 1]);
	ret = (ret + 1LL * (2 * components - 2 + alive_ends) * f(alive_ends, i + 1, components, sm)) % MOD;
	if(components) 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;
	if(alive_ends) ret = (ret + 1LL * alive_ends * f(alive_ends - 1, i + 1, components + 1, sm)) % MOD;
	if(components) 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, 0, 0, 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 72 ms 136160 KB Output is correct
2 Correct 65 ms 136276 KB Output is correct
3 Correct 65 ms 136272 KB Output is correct
4 Incorrect 70 ms 136496 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 136192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 136160 KB Output is correct
2 Correct 65 ms 136276 KB Output is correct
3 Correct 65 ms 136272 KB Output is correct
4 Incorrect 70 ms 136496 KB Output isn't correct
5 Halted 0 ms 0 KB -