제출 #1065919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1065919		AkramElOmrani	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	191 ms	186156 KiB

skyscraper

#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) {
	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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80