oj.uz

Submission #1065921

# Submission time Handle Problem Language Result Execution time Memory
1065921 2024-08-19T13:08:33 Z AkramElOmrani Skyscraper (JOI16_skyscraper) C++17
100 / 100
 190 ms 321168 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")

#define ll long long
#define int ll
#define ios ios_base::sync_with_stdio(0);cin.tie(0);

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int gen(int a, int b) {return (ll)rng() % (b - a + 1) + a;}



const int mod = 1e9 + 7; // 998244353

int add(int a, int b) {
	b %= mod;
	a += b;
	if(a >= mod) {
		a -= mod;
	}
	return a;
}

vector<int> a;

int n, L;
int dp[103][103][1003][2][2];

int f(int i, int j, int k, int l, int r) {
	int cost = k + (2 * j + l + r) * (a[i] - a[i - 1]);
	if(cost > L || j < 0) return 0;
	if(i == n) return (j == 0);
	if(dp[i][j][k][l][r] != -1) {
		return dp[i][j][k][l][r];
	}
	int ans = 0;

	// open a new interval that is non extreme
	ans = add(ans, f(i + 1, j + 1, cost, l, r));

	// add to the left or to the right one way to do it each
	ans = add(ans, f(i + 1, j, cost, 1, r));
	ans = add(ans, f(i + 1, j, cost, l, 1));

	// pick a non extreme interval and add this to it (2 * j possible endpoints)
	ans = add(ans, f(i + 1, j, cost, l, r) * (j * 2) ) ;

	// remove an interval by sticking it to an extreme interval to the left
	ans = add(ans, f(i + 1, j - 1, cost, 1, r)  * j);
	// remove an interval by sticking it to an extreme interval to the right
	ans = add(ans, f(i + 1, j - 1, cost, l, 1)  * j);


	// close any two non extreme intervals by sticking them together (you have j * (j - 1) pairs of them)
	ans = add(ans, f(i + 1, j - 1, cost, l, r) * j * (j - 1));

	// dbg(ans)

	return dp[i][j][k][l][r] = ans;
}

signed main()
{
	ios
	cin >> n >> L;
	for(int i = 0; i <= n; ++i) {
		for(int j = 0; j <= n; ++j) {
			for(int k = 0; k <= L; ++k) {
				for(int l = 0; l <= 1; ++l) {
					for(int r = 0; r <= 1; ++r) {
						dp[i][j][k][l][r] = -1;
					}
				}
			}
		}
	}
	a.resize(n);
	for(int& x : a) cin >> x;
	sort(a.rbegin(), a.rend());
	a.emplace_back(a[n - 1]);
	reverse(a.begin(), a.end());

	// for(int i = 1; i <= n; ++i) {
	// 	for(int j = 1; j <= i; ++j) {
	// 		for(int l = 0; l <= 2; ++l) {
	// 			int cost = (2 * j - l) * (a[i] - a[i - 1]);
	// 			if(i + j + 1 - l > n) continue;
	// 			for(int k = cost; k <= L; ++k) {
	// 				// add new interval
	// 				dp[i][j][k][l] += dp[i - 1][j - 1][k - cost][l];
	// 				if(l == 1) {
	// 					dp[i][j][k][l] += 2 * dp[i - 1][j - 1][k - cost][l - 1];
	// 				} else if(l == 2) {
	// 					dp[i][j][k][l] += 1 * dp[i - 1][j - 1][k - cost][l - 1];
	// 				}

	// 				// add to existing interval
	// 				dp[i][j][k][l] += (2 * j - l) * dp[i - 1][j][k - cost][l];



	// 				if(m == 2 && i == n) {
	// 					dp[i][j][k][l] += dp[i - 1][j + 1][k - cost][l];
	// 				} else {
	// 					dp[i][j][k][l] += j * (j + 1 - l) * dp[i - 1][j + 1][k - cost][l];
	// 				}
	// 				// dbg(i, j, k, l, dp[i][j][k][l])
	// 			}
	// 		}
	// 	}
	// }
	// mint ans = 0;
	// for(int k = 0; k <= L; ++k) {
	// 	ans += dp[n][1][k][2];
	// }
	cout << f(1, 0, 0, 0, 0) << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 604 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 0 ms 1116 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 0 ms 1116 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 604 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 0 ms 1116 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 0 ms 1116 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Correct 1 ms 1884 KB Output is correct
13 Correct 1 ms 1628 KB Output is correct
14 Correct 1 ms 1884 KB Output is correct
15 Correct 1 ms 1884 KB Output is correct
16 Correct 1 ms 1884 KB Output is correct
17 Correct 1 ms 1628 KB Output is correct
18 Correct 1 ms 1628 KB Output is correct
19 Correct 1 ms 1884 KB Output is correct
20 Correct 1 ms 1884 KB Output is correct
21 Correct 4 ms 9308 KB Output is correct
22 Correct 171 ms 186196 KB Output is correct
23 Correct 190 ms 321108 KB Output is correct
24 Correct 170 ms 278356 KB Output is correct
25 Correct 181 ms 321168 KB Output is correct
26 Correct 175 ms 311116 KB Output is correct
27 Correct 72 ms 119644 KB Output is correct
28 Correct 83 ms 137300 KB Output is correct
29 Correct 149 ms 224084 KB Output is correct
30 Correct 190 ms 321108 KB Output is correct