oj.uz

Submission #1046788

# Submission time Handle Problem Language Result Execution time Memory
1046788 2024-08-06T23:44:27 Z idiotcomputer Skyscraper (JOI16_skyscraper) C++11
20 / 100
 366 ms 524288 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 3 ms 5468 KB Output is correct
6 Correct 3 ms 5464 KB Output is correct
7 Correct 3 ms 5464 KB Output is correct
8 Correct 4 ms 5468 KB Output is correct
9 Correct 4 ms 5532 KB Output is correct
10 Correct 4 ms 5468 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11356 KB Output is correct
2 Correct 10 ms 15196 KB Output is correct
3 Correct 12 ms 15272 KB Output is correct
4 Correct 12 ms 15232 KB Output is correct
5 Correct 12 ms 15248 KB Output is correct
6 Correct 11 ms 15196 KB Output is correct
7 Correct 13 ms 15060 KB Output is correct
8 Correct 14 ms 15272 KB Output is correct
9 Correct 10 ms 15196 KB Output is correct
10 Correct 11 ms 15092 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 3 ms 5468 KB Output is correct
6 Correct 3 ms 5464 KB Output is correct
7 Correct 3 ms 5464 KB Output is correct
8 Correct 4 ms 5468 KB Output is correct
9 Correct 4 ms 5532 KB Output is correct
10 Correct 4 ms 5468 KB Output is correct
11 Correct 8 ms 11356 KB Output is correct
12 Correct 10 ms 15196 KB Output is correct
13 Correct 12 ms 15272 KB Output is correct
14 Correct 12 ms 15232 KB Output is correct
15 Correct 12 ms 15248 KB Output is correct
16 Correct 11 ms 15196 KB Output is correct
17 Correct 13 ms 15060 KB Output is correct
18 Correct 14 ms 15272 KB Output is correct
19 Correct 10 ms 15196 KB Output is correct
20 Correct 11 ms 15092 KB Output is correct
21 Correct 103 ms 115972 KB Output is correct
22 Correct 366 ms 435196 KB Output is correct
23 Runtime error 201 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -