Submission #1046788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046788		idiotcomputer	Skyscraper (JOI16_skyscraper)	C++11	20 / 100	366 ms	524288 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 

const ll mod = 1e9+7;



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n,l;
	cin >> n >> l;

	vector<int> h(n);
	for (int i = 0; i < n; i++) cin >> h[i];
	sort(h.begin(),h.end());
	//2000 is 0
	ll dp[n][n+1][3005][3];
	memset(dp,0,sizeof(dp));
	dp[0][1][2000-2*h[0]][2] = 1;
	dp[0][1][2000-h[0]][1] = 2;
	int v;
	for (int i = 1; i < n; i++){
		for (int j = 1; j < n; j++){
			for (int k = 0; k < 3005; k++){
				//appending
				dp[i][j][k][0] += dp[i-1][j][k][0] * 2 * (j-1);
				dp[i][j][k][1] += dp[i-1][j][k][1] * (2 * j - 1);
				dp[i][j][k][2] += dp[i-1][j][k][2] * 2 * (j);
				//border
				v = h[i];
				if (k >= v){
					dp[i][j][k][0] += dp[i-1][j][k-v][1] * (j-1);
					if (i == n-1) dp[i][j][k][0] += dp[i-1][j][k-v][1];
					dp[i][j][k][1] += dp[i-1][j][k-v][2] * 2 * j;
				}

				//combining
				v = 2*h[i];
				if (k >= v){
					dp[i][j][k][0] += dp[i-1][j+1][k-v][0] * (j*(j-1));
					if (i == n-1) dp[i][j][k][0] += dp[i-1][j+1][k-v][0];
					dp[i][j][k][1] += dp[i-1][j+1][k-v][1] * (j) * j;
					dp[i][j][k][2] += dp[i-1][j+1][k-v][2] * (j+1) * j;
				}
				
				//new cc
				if (k+v < 3005){
					dp[i][j][k][0] += dp[i-1][j-1][k+v][0];
					dp[i][j][k][1] += dp[i-1][j-1][k+v][1];
					dp[i][j][k][2] += dp[i-1][j-1][k+v][2];
				}
				//border
				v = h[i];
				if (k+v < 3005){
					dp[i][j][k][0] += dp[i-1][j-1][k+v][1];
					dp[i][j][k][1] += dp[i-1][j-1][k+v][2]*2;
				}
				for (int t = 0; t < 3; t++) dp[i][j][k][t] = (dp[i][j][k][t])%mod;
			}
		}
	}
	if (n == 1) dp[0][1][2000][0] = 1;
	ll res = 0;
	for (int i = 2000; i <= 2000+l; i++) res = (res + dp[n-1][1][i][0]) % mod;

	cout << res << '\n';
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80