oj.uz

답안 #448079

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
448079 2021-07-28T17:53:36 Z AmShZ Skyscraper (JOI16_skyscraper) C++11
100 / 100
 252 ms 82008 KB 
//khodaya khodet komak kon
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 1e2 + 10;
const int xm = 1e3 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 1e9 + 7;//998244353;
const int base = 257;

int n, a[xn], L, dp[xn][xn][2][2][xm], ans;

int main(){
	fast_io;

	cin >> n >> L;
	for (int i = 1; i <= n; ++ i)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	for (int i = 0; i < 2; ++ i)
		for (int j = 0; j < 2; ++ j)
			dp[1][1][i][j][0] = 1;
	for (int i = 1; i < n; ++ i){
		for (int j = 1; j <= i; ++ j){
			for (int f1 = 0; f1 < 2; ++ f1){
				for (int f2 = 0; f2 < 2; ++ f2){
					for (int k = 0; k <= L; ++ k){
						int kp = k + (j + j - 2 + f1 + f2) * (a[i + 1] - a[i]);
						if (L < kp)
							continue;
						dp[i + 1][j][f1][f2][kp] = (dp[i + 1][j][f1][f2][kp] + 1ll * dp[i][j][f1][f2][k] * (j + j - 2) % mod) % mod;
						dp[i + 1][j + 1][f1][f2][kp] = (dp[i + 1][j + 1][f1][f2][kp] + 1ll * dp[i][j][f1][f2][k] * (j - 1) % mod) % mod;
						dp[i + 1][j - 1][f1][f2][kp] = (dp[i + 1][j - 1][f1][f2][kp] + 1ll * dp[i][j][f1][f2][k] * (j - 1) % mod) % mod;
						if (f1){
							for (int f3 = 0; f3 < 2; ++ f3){
								dp[i + 1][j][f3][f2][kp] = (dp[i + 1][j][f3][f2][kp] + dp[i][j][f1][f2][k]) % mod;
								dp[i + 1][j + 1][f3][f2][kp] = (dp[i + 1][j + 1][f3][f2][kp] + dp[i][j][f1][f2][k]) % mod;
							}
						}
						if (f2){
							for (int f3 = 0; f3 < 2; ++ f3){
								dp[i + 1][j][f1][f3][kp] = (dp[i + 1][j][f1][f3][kp] + dp[i][j][f1][f2][k]) % mod;
								dp[i + 1][j + 1][f1][f3][kp] = (dp[i + 1][j + 1][f1][f3][kp] + dp[i][j][f1][f2][k]) % mod;
							}
						}
					}
				}
			}
		}
	}
	for (int i = 0; i <= L; ++ i)
		ans = (ans + dp[n][1][0][0][i]) % mod;
	cout << ans << endl;

	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 960 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 1 ms 972 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1740 KB Output is correct
2 Correct 2 ms 1740 KB Output is correct
3 Correct 2 ms 2124 KB Output is correct
4 Correct 2 ms 1740 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 2 ms 2124 KB Output is correct
7 Correct 2 ms 1980 KB Output is correct
8 Correct 2 ms 2124 KB Output is correct
9 Correct 2 ms 2124 KB Output is correct
10 Correct 2 ms 1740 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 960 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 1 ms 972 KB Output is correct
11 Correct 2 ms 1740 KB Output is correct
12 Correct 2 ms 1740 KB Output is correct
13 Correct 2 ms 2124 KB Output is correct
14 Correct 2 ms 1740 KB Output is correct
15 Correct 2 ms 1868 KB Output is correct
16 Correct 2 ms 2124 KB Output is correct
17 Correct 2 ms 1980 KB Output is correct
18 Correct 2 ms 2124 KB Output is correct
19 Correct 2 ms 2124 KB Output is correct
20 Correct 2 ms 1740 KB Output is correct
21 Correct 8 ms 10828 KB Output is correct
22 Correct 198 ms 50520 KB Output is correct
23 Correct 249 ms 66552 KB Output is correct
24 Correct 232 ms 73288 KB Output is correct
25 Correct 252 ms 65812 KB Output is correct
26 Correct 224 ms 67636 KB Output is correct
27 Correct 116 ms 81916 KB Output is correct
28 Correct 135 ms 82008 KB Output is correct
29 Correct 215 ms 81416 KB Output is correct
30 Correct 250 ms 66024 KB Output is correct