oj.uz

Submission #112364

# Submission time Handle Problem Language Result Execution time Memory
112364 2019-05-19T06:16:36 Z Mahdi_Jfri Skyscraper (JOI16_skyscraper) C++14
100 / 100
 580 ms 69772 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e2 + 20;
const int maxl = 1e3 + 20;
const int mod = 1e9 + 7;

int dp[maxn][maxn][maxl][2][2] , a[maxn];

inline void mkay(int &a)
{
	if(a >= mod)
		a -= mod;
	else if(a < 0)
		a += mod;
}

void reval(int i , int j , int k , int x , int y , int val)
{
	if(k < maxl)
		mkay(dp[i][j][k][x][y] += val);
}

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

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

	for(int i = 1; i <= n; i++)
		cin >> a[i];

	sort(a + 1 , a + n + 1);

	for(int x = 0; x < 2; x++)
		for(int y = 0; y < 2; y++)
			dp[1][1][0][x][y] = 1;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= i; j++)
			for(int k = 0; k <= l; k++)
				for(int x = 0; x < 2; x++)
					for(int y = 0; y < 2; y++)
					{
						int dif = a[i + 1] - a[i] , val = dp[i][j][k][x][y];
						int tmp = (2 * j - 2 + x + y) * dif;

						if(x)
						{
							reval(i + 1 , j , k + tmp , 1 , y , val);
							reval(i + 1 , j , k + tmp , 0 , y , val);

							reval(i + 1 , j + 1 , k + tmp , 1 , y , val);
							reval(i + 1 , j + 1 , k + tmp , 0 , y , val);
						}
						if(y)
						{
							reval(i + 1 , j , k + tmp , x , 1 , val);
							reval(i + 1 , j , k + tmp , x , 0 , val);

							reval(i + 1 , j + 1 , k + tmp , x , 1 , val);
							reval(i + 1 , j + 1 , k + tmp , x , 0 , val);
						}

						val = 1LL * val * (j - 1) % mod;
						if(j >= 2)
							reval(i + 1 , j - 1 , k + tmp , x , y , val);

						reval(i + 1 , j , k + tmp , x , y , val * 2 % mod);
						reval(i + 1 , j + 1 , k + tmp , x , y , val);
					}

	int sum = 0;
	for(int i = 0; i <= l; i++)
		mkay(sum += dp[n][1][i][0][0]);

	cout << sum << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 6 ms 1024 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 4 ms 768 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 6 ms 1024 KB Output is correct
10 Correct 3 ms 640 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1024 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 4 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 3 ms 1024 KB Output is correct
8 Correct 3 ms 1068 KB Output is correct
9 Correct 4 ms 1024 KB Output is correct
10 Correct 4 ms 1152 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 6 ms 1024 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 4 ms 768 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 6 ms 1024 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 4 ms 1024 KB Output is correct
12 Correct 5 ms 1280 KB Output is correct
13 Correct 3 ms 1024 KB Output is correct
14 Correct 4 ms 1280 KB Output is correct
15 Correct 5 ms 1280 KB Output is correct
16 Correct 5 ms 1152 KB Output is correct
17 Correct 3 ms 1024 KB Output is correct
18 Correct 3 ms 1068 KB Output is correct
19 Correct 4 ms 1024 KB Output is correct
20 Correct 4 ms 1152 KB Output is correct
21 Correct 11 ms 4608 KB Output is correct
22 Correct 505 ms 51036 KB Output is correct
23 Correct 562 ms 59512 KB Output is correct
24 Correct 580 ms 69772 KB Output is correct
25 Correct 580 ms 58744 KB Output is correct
26 Correct 557 ms 62704 KB Output is correct
27 Correct 236 ms 41844 KB Output is correct
28 Correct 289 ms 46320 KB Output is correct
29 Correct 535 ms 67148 KB Output is correct
30 Correct 574 ms 58616 KB Output is correct