oj.uz

Submission #1043799

# Submission time Handle Problem Language Result Execution time Memory
1043799 2024-08-04T18:25:08 Z lozergam Skyscraper (JOI16_skyscraper) C++17
100 / 100
 49 ms 51024 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define For(i, n) for(int (i) = 0 ; (i) < (n); (i)++)
#define debug(x) cout << #x << " : " << x << endl << flush
#define endl '\n'
#define sz(x) (ll)x.size()

const ll MOD = 1e9 + 7;
const ll maxn = 103;
const ll maxl = 1005;
ll dp[maxn][maxn][maxl][3];
ll a[maxn];
ll n, l;

int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	
	cin >> n >> l;
	
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	
	if(n == 1)
	{
		cout << 1 << endl;
		exit(0);
	}
	
	sort(a + 1, a + n + 1);
	a[n + 1] = 10000;
	
	dp[0][0][0][0] = 1;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= i; j++)
			for(int k = 0; k <= l; k++)
				for(int m = 0; m <= 2; m++)
				{
					ll delta = (2 * j - m) * (a[i + 1] - a[i]);
					
					if(delta > k)continue;
					if(i + j + 1 - m > n)continue;
					//new element make a new comp and dont have end point
					dp[i][j][k][m] += dp[i - 1][j - 1][k - delta][m];
					
					//new element make a new comp and have end point
					if(m == 1)
						dp[i][j][k][m] += 2 * dp[i - 1][j - 1][k - delta][0];
						
					else if(m == 2)
						dp[i][j][k][m] += dp[i - 1][j - 1][k - delta][1];
						
					//new element go to one of the comps but not the endpoint
					dp[i][j][k][m] += (2 * j - m) * dp[i - 1][j][k - delta][m];
					
					//new element go to one of the comps and endpoint
					if(m == 1)
						dp[i][j][k][m] += (2 * j) * dp[i - 1][j][k - delta][0];
					
					else if(m == 2 and i == n)
						dp[i][j][k][m] += dp[i - 1][j][k - delta][1];
					
					else if(m == 2)
						dp[i][j][k][m] += (j - 1) * dp[i - 1][j][k - delta][1];
						
					//new element combone two comps
					if(m == 0)
						dp[i][j][k][m] += (j * (j + 1)) * dp[i - 1][j + 1][k - delta][0];
					else if(m == 1)
						dp[i][j][k][m] += (j * (j - 1) + j) * dp[i - 1][j + 1][k - delta][1];
					else if(i == n)
						dp[i][j][k][m] += dp[i - 1][j + 1][k - delta][2];
					else
						dp[i][j][k][m] += ((2 * (j - 1)) + ((j - 1) * (j - 2))) * dp[i - 1][j + 1][k - delta][2];
						
					dp[i][j][k][m] %= MOD;
				}
				
	ll ans = 0;	
	For(i, l+1)ans += dp[n][1][i][2];
	
	cout << ans % MOD << endl;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define For(i, n) for(int (i) = 0 ; (i) < (n); (i)++)
      |                           ^
skyscraper.cpp:85:2: note: in expansion of macro 'For'
   85 |  For(i, l+1)ans += dp[n][1][i][2];
      |  ^~~

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 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 0 ms 616 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 860 KB Output is correct
10 Correct 0 ms 604 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 0 ms 616 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 860 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 604 KB Output is correct
17 Correct 0 ms 604 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 0 ms 604 KB Output is correct
21 Correct 2 ms 2396 KB Output is correct
22 Correct 33 ms 35956 KB Output is correct
23 Correct 47 ms 47696 KB Output is correct
24 Correct 43 ms 46908 KB Output is correct
25 Correct 49 ms 50768 KB Output is correct
26 Correct 41 ms 46168 KB Output is correct
27 Correct 17 ms 23640 KB Output is correct
28 Correct 21 ms 26972 KB Output is correct
29 Correct 34 ms 41320 KB Output is correct
30 Correct 47 ms 51024 KB Output is correct