oj.uz

Submission #112381

# Submission time Handle Problem Language Result Execution time Memory
112381 2019-05-19T07:34:59 Z MAMBA Skyscraper (JOI16_skyscraper) C++17
100 / 100
 148 ms 5676 KB 
#include <bits/stdc++.h> 

using namespace std;

#define rep(i , j , k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(),x.end()

typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef long double ld;
typedef complex<ld> point;

inline void fileIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}

template<class T , class S>
inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
template<class T , class S>
inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }

constexpr int N = 100 + 10;
constexpr int L = 1010;

constexpr int MOD = 1e9 + 7;

template<typename T>
inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
template<typename S, typename T>
inline S add(S &l, T r) { return mod(l += r); }

int n , l;

ll dp[2][N][L][3], arr[N];


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

#ifndef LOCAL
	//	fileIO("forbidden1");
#endif

	cin >> n >> l;

	if (n == 1) return cout << 1 << endl, 0;

	rep(i , 0 , n) cin >> arr[i];
	sort(arr, arr + n);
	arr[n] = 1e9;
	rep(i , 0 , n)
		arr[i] = arr[i + 1] - arr[i];

	dp[0][1][arr[0] << 1][0] = 1;
	dp[0][1][arr[0]][1] = 2;

	rep(i , 0 , n - 1) {
		int id = i & 1;
		rep(j , 1 , i + 2) {
			rep(z , 0 , l + 1) {
				// sar o tah 0 baste
				{
					ll me = dp[id][j][z][0];
					ll EN = 2 * j;
					// merge
					if (j > 1 && (EN - 2) * arr[i + 1] + z <= l)
						add(dp[id ^ 1][j - 1][(EN - 2) * arr[i + 1] + z][0] , (j - 1) * me);
					// sar ya tah
					//     endpoint bashe
					if ((EN - 1) * arr[i + 1] + z <= l)
						add(dp[id ^ 1][j][(EN - 1) * arr[i + 1] + z][1] , 2 * me);
					// 	   on vasata bashe
					if  (EN	* arr[i + 1] + z <= l)
						add(dp[id ^ 1][j][EN	* arr[i + 1] + z][0] , me * EN); 
					// jadid
					if ((EN + 2) * arr[i + 1] + z <= l) 
						add(dp[id ^ 1][j + 1][(EN + 2) * arr[i + 1] + z][0] , me * (j + 1)); 
					if ((EN + 1) * arr[i + 1] + z <= l)
						add(dp[id ^ 1][j + 1][(EN + 1) * arr[i + 1] + z][1] , me * 2);

				}
				// sar o tah 1 baste
				{
					ll me = dp[id][j][z][1];
					ll EN = 2 * j - 1;
					// merge
					if (j > 1 && (EN - 2) * arr[i + 1] + z <= l) 
						add(dp[id ^ 1][j - 1][(EN - 2) * arr[i + 1] + z][1] , (j - 1) * me); 
					// sar ya tah
					//   	endpoint
					if ((EN - 1) * arr[i + 1] + z <= l)
						add(dp[id ^ 1][j][(EN - 1) * arr[i + 1] + z][2] , me);
					//  	on vasata
					if  (EN	* arr[i + 1] + z <= l)
						add(dp[id ^ 1][j][EN	* arr[i + 1] + z][1] , me * EN); 
					// jadid
					if ((EN + 2) * arr[i + 1] + z <= l) 
						add(dp[id ^ 1][j + 1][(EN + 2) * arr[i + 1] + z][1] , me * j); 
					if ((EN + 1) * arr[i + 1] + z <= l)
						add(dp[id ^ 1][j + 1][(EN + 1) * arr[i + 1] + z][2] , me);
				}
				// sar o tah 2 baste
				{
					ll me = dp[id][j][z][2];
					ll EN = 2 * j - 2;
					// merge
					if (j > 1 && (EN - 2) * arr[i + 1] + z <= l) 
						add(dp[id ^ 1][j - 1][(EN - 2) * arr[i + 1] + z][2] , (j - 1) * me); 
					// sar ya tah
					//  	on vasata
					if  (EN	* arr[i + 1] + z <= l)
						add(dp[id ^ 1][j][EN	* arr[i + 1] + z][2] , me * EN); 
					// jadid
					if ((EN + 2) * arr[i + 1] + z <= l) 
						add(dp[id ^ 1][j + 1][(EN + 2) * arr[i + 1] + z][2] , me * (j - 1)); 	
				}
			}
		}
		memset(dp[id] , 0 , sizeof(dp[id]));
	}
/*
	rep(j , 1 , n + 1)
	   rep(z , 0 , l + 1) {
			cout << j << ' '<< z << ' '<< dp[(n - 1) & 1][j][z][2] << endl;
	   }	*/   
	ll res = 0;
	rep(i , 0 , l + 1) {
		add(res , dp[(n - 1) & 1][1][i][2]);
	}
	cout << res << endl;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 2944 KB Output is correct
3 Correct 5 ms 5504 KB Output is correct
4 Correct 6 ms 5632 KB Output is correct
5 Correct 7 ms 5504 KB Output is correct
6 Correct 7 ms 5676 KB Output is correct
7 Correct 7 ms 5632 KB Output is correct
8 Correct 7 ms 5632 KB Output is correct
9 Correct 7 ms 5632 KB Output is correct
10 Correct 6 ms 5504 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5504 KB Output is correct
2 Correct 7 ms 5504 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 8 ms 5632 KB Output is correct
6 Correct 8 ms 5632 KB Output is correct
7 Correct 7 ms 5632 KB Output is correct
8 Correct 8 ms 5632 KB Output is correct
9 Correct 8 ms 5632 KB Output is correct
10 Correct 7 ms 5632 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 4 ms 2944 KB Output is correct
3 Correct 5 ms 5504 KB Output is correct
4 Correct 6 ms 5632 KB Output is correct
5 Correct 7 ms 5504 KB Output is correct
6 Correct 7 ms 5676 KB Output is correct
7 Correct 7 ms 5632 KB Output is correct
8 Correct 7 ms 5632 KB Output is correct
9 Correct 7 ms 5632 KB Output is correct
10 Correct 6 ms 5504 KB Output is correct
11 Correct 7 ms 5504 KB Output is correct
12 Correct 7 ms 5504 KB Output is correct
13 Correct 7 ms 5632 KB Output is correct
14 Correct 8 ms 5504 KB Output is correct
15 Correct 8 ms 5632 KB Output is correct
16 Correct 8 ms 5632 KB Output is correct
17 Correct 7 ms 5632 KB Output is correct
18 Correct 8 ms 5632 KB Output is correct
19 Correct 8 ms 5632 KB Output is correct
20 Correct 7 ms 5632 KB Output is correct
21 Correct 11 ms 5504 KB Output is correct
22 Correct 103 ms 5632 KB Output is correct
23 Correct 148 ms 5596 KB Output is correct
24 Correct 128 ms 5632 KB Output is correct
25 Correct 137 ms 5504 KB Output is correct
26 Correct 121 ms 5632 KB Output is correct
27 Correct 54 ms 5504 KB Output is correct
28 Correct 63 ms 5632 KB Output is correct
29 Correct 106 ms 5632 KB Output is correct
30 Correct 139 ms 5504 KB Output is correct