oj.uz

Submission #362397

# Submission time Handle Problem Language Result Execution time Memory
362397 2021-02-03T04:41:44 Z Blerargh Skyscraper (JOI16_skyscraper) C++17
15 / 100
 2 ms 1772 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MAXN = 105;
const ll COST = 1005;
const ll MOD = 1e9+7;

ll dp[MAXN][MAXN][COST][3];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll N, L;
	cin >> N >> L;
	
	dp[0][0][0][0] = 1;
	
	vector<ll> heights;
	for (int i=0; i<N; i++){
		ll x;
		cin >> x;
		heights.push_back(x);
	}
	heights.push_back(0);
	sort(heights.begin(), heights.end());
	
	for (int i=1; i<=N; i++){
		ll C = heights[i] - heights[i-1];
		if (i==1) C = 0;
		for (int j=1; j<=N; j++){
			for (int k=0; k<=L; k++){
				for (int l=0; l<3; l++){
					//adding a component without closing any end
					if (k - (2*j-2-l)*C >= 0) dp[i][j][k][l] += dp[i-1][j-1][k - (2*j-2-l)*C][l];
					
					//adding a component and closing one end
					if (k - (2*j-1-l)*C >= 0 && l){
						if (l==1) dp[i][j][k][l] += dp[i-1][j-1][k - (2*j-1-l)*C][l-1] * 2;
						if (l==2) dp[i][j][k][l] += dp[i-1][j-1][k - (2*j-1-l)*C][l-1];
					}
					
					//adding to a component without closing any end
					if (k - (2*j-l)*C >= 0) dp[i][j][k][l] += dp[i-1][j][k - (2*j-l)*C][l] * (2*j - l);
					
					//adding to a component and closing one end
					if (i==N && j==1 && k-C>=0 && l==2) dp[i][j][k][l] += dp[i-1][j][k - C][l-1];
					else if (k - (2*j-l+1)*C >= 0){
						if (l == 1) dp[i][j][k][l] += dp[i-1][j][k - (2*j-l+1)*C][l-1] * (2 * j);
						if (l == 2) dp[i][j][k][l] += dp[i-1][j][k - (2*j-l+1)*C][l-1] * (j - 1);
					}
					
					//merging two components
					if (i==N && j==1 && k-2*C>=0 && l==2) dp[i][j][k][l] += dp[i-1][j+1][k - 2*C][l];
					else if (k - (2*j+2-l)*C >= 0) {
						if (l==0) dp[i][j][k][l] += dp[i-1][j+1][k - (2*j+2-l)*C][l] * (j+1) * j;
						if (l==1) dp[i][j][k][l] += dp[i-1][j+1][k - (2*j+2-l)*C][l] * j * j;
						if (l==2) dp[i][j][k][l] += dp[i-1][j+1][k - (2*j+2-l)*C][l] * (j-1) * j; 
					}
					
					dp[i][j][k][l] %= MOD;
				}
			}
		}
	}
	
	ll ans=0;
	for (int cost=0; cost<=L; cost++){
		ans += dp[N][1][cost][2];
		ans%=MOD;
	}
	cout << ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 2 ms 1644 KB Output is correct
3 Correct 2 ms 1388 KB Output is correct
4 Correct 2 ms 1644 KB Output is correct
5 Correct 2 ms 1772 KB Output is correct
6 Correct 2 ms 1644 KB Output is correct
7 Correct 1 ms 1280 KB Output is correct
8 Correct 2 ms 1388 KB Output is correct
9 Correct 2 ms 1516 KB Output is correct
10 Correct 2 ms 1516 KB Output is correct

Subtask #3
0 / 80.0

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