oj.uz

답안 #1086344

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1086344 2024-09-10T09:37:53 Z Raiden Skyscraper (JOI16_skyscraper) C++14
15 / 100
 73 ms 136528 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;
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 136276 KB Output is correct
2 Correct 69 ms 136280 KB Output is correct
3 Correct 62 ms 136272 KB Output is correct
4 Correct 61 ms 136272 KB Output is correct
5 Correct 63 ms 136272 KB Output is correct
6 Incorrect 65 ms 136276 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 136272 KB Output is correct
2 Correct 73 ms 136252 KB Output is correct
3 Correct 65 ms 136528 KB Output is correct
4 Correct 65 ms 136120 KB Output is correct
5 Correct 64 ms 136144 KB Output is correct
6 Correct 65 ms 136272 KB Output is correct
7 Correct 64 ms 136160 KB Output is correct
8 Correct 64 ms 136276 KB Output is correct
9 Correct 65 ms 136240 KB Output is correct
10 Correct 63 ms 136272 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 136276 KB Output is correct
2 Correct 69 ms 136280 KB Output is correct
3 Correct 62 ms 136272 KB Output is correct
4 Correct 61 ms 136272 KB Output is correct
5 Correct 63 ms 136272 KB Output is correct
6 Incorrect 65 ms 136276 KB Output isn't correct
7 Halted 0 ms 0 KB -