oj.uz

Submission #44672

# Submission time Handle Problem Language Result Execution time Memory
44672 2018-04-04T17:48:02 Z IvanC Skyscraper (JOI16_skyscraper) C++17
100 / 100
 401 ms 321228 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXL = 1002;
const int MAXN = 101;
const ll MOD = 1e9 + 7;
ll dp[MAXN][MAXN][2][2][MAXL],N,L,V[MAXN];
ll solve(ll pos,ll cmp,ll lcmp,ll rcmp,ll penalty){
	if(cmp < 0) return 0;
	if(dp[pos][cmp][lcmp][rcmp][penalty] != -1) return dp[pos][cmp][lcmp][rcmp][penalty]; 
	ll penalty_now = penalty;
	if(pos > 1) penalty_now += (2*cmp + lcmp + rcmp)*abs(V[pos] - V[pos-1]);
	if(penalty_now > L) return dp[pos][cmp][lcmp][rcmp][penalty] = 0;
	if(pos == N){
		if(cmp == 0) return dp[pos][cmp][lcmp][rcmp][penalty] = 1;
		else return dp[pos][cmp][lcmp][rcmp][penalty] = 0;
	}
	ll tot = 0;
	tot += solve(pos+1,cmp,1,rcmp,penalty_now);
	tot += solve(pos+1,cmp-1,1,rcmp,penalty_now)*cmp;
	tot += solve(pos+1,cmp,lcmp,1,penalty_now);
	tot += solve(pos+1,cmp-1,lcmp,1,penalty_now)*cmp;
	tot += solve(pos+1,cmp,lcmp,rcmp,penalty_now)*(2*cmp);
	tot += solve(pos+1,cmp+1,lcmp,rcmp,penalty_now);
	tot += solve(pos+1,cmp-1,lcmp,rcmp,penalty_now)*cmp*(cmp-1);
	return dp[pos][cmp][lcmp][rcmp][penalty] = (tot % MOD);
}
int main(){
	memset(dp,-1,sizeof(dp));
	cin >> N >> L;
	for(int i = 1;i<=N;i++) cin >> V[i];
	sort(V+1,V+N+1);
	cout << solve(1,0,0,0,0) << endl;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 320376 KB Output is correct
2 Correct 232 ms 320508 KB Output is correct
3 Correct 224 ms 320588 KB Output is correct
4 Correct 232 ms 320600 KB Output is correct
5 Correct 222 ms 320616 KB Output is correct
6 Correct 230 ms 320644 KB Output is correct
7 Correct 223 ms 320724 KB Output is correct
8 Correct 220 ms 320724 KB Output is correct
9 Correct 223 ms 320724 KB Output is correct
10 Correct 221 ms 320724 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 320736 KB Output is correct
2 Correct 223 ms 320796 KB Output is correct
3 Correct 222 ms 320800 KB Output is correct
4 Correct 226 ms 320928 KB Output is correct
5 Correct 223 ms 320928 KB Output is correct
6 Correct 221 ms 320928 KB Output is correct
7 Correct 227 ms 320944 KB Output is correct
8 Correct 227 ms 321056 KB Output is correct
9 Correct 232 ms 321056 KB Output is correct
10 Correct 222 ms 321056 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 320376 KB Output is correct
2 Correct 232 ms 320508 KB Output is correct
3 Correct 224 ms 320588 KB Output is correct
4 Correct 232 ms 320600 KB Output is correct
5 Correct 222 ms 320616 KB Output is correct
6 Correct 230 ms 320644 KB Output is correct
7 Correct 223 ms 320724 KB Output is correct
8 Correct 220 ms 320724 KB Output is correct
9 Correct 223 ms 320724 KB Output is correct
10 Correct 221 ms 320724 KB Output is correct
11 Correct 221 ms 320736 KB Output is correct
12 Correct 223 ms 320796 KB Output is correct
13 Correct 222 ms 320800 KB Output is correct
14 Correct 226 ms 320928 KB Output is correct
15 Correct 223 ms 320928 KB Output is correct
16 Correct 221 ms 320928 KB Output is correct
17 Correct 227 ms 320944 KB Output is correct
18 Correct 227 ms 321056 KB Output is correct
19 Correct 232 ms 321056 KB Output is correct
20 Correct 222 ms 321056 KB Output is correct
21 Correct 221 ms 321056 KB Output is correct
22 Correct 401 ms 321056 KB Output is correct
23 Correct 334 ms 321080 KB Output is correct
24 Correct 341 ms 321228 KB Output is correct
25 Correct 346 ms 321228 KB Output is correct
26 Correct 322 ms 321228 KB Output is correct
27 Correct 271 ms 321228 KB Output is correct
28 Correct 292 ms 321228 KB Output is correct
29 Correct 352 ms 321228 KB Output is correct
30 Correct 346 ms 321228 KB Output is correct