oj.uz

Submission #724039

# Submission time Handle Problem Language Result Execution time Memory
724039 2023-04-14T15:53:23 Z Zanite Skyscraper (JOI16_skyscraper) C++17
100 / 100
 127 ms 130444 KB 
// 赤コーダーになりたい
// お願い いいですか？

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// Pragmas
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
using namespace std;
using namespace __gnu_pbds;

// Data types
using si	= short int;
using ll	= long long;
using lll	= __int128;
using ld	= long double;

// Pairs
using pii	= pair<int, int>;
using psi	= pair<si, si>;
using pll	= pair<ll, ll>;
using plll	= pair<lll, lll>;
using pld	= pair<ld, ld>;
#define fi	first
#define se	second

// For
#define Frue(i, n, N)		for (int i = (n); i <= (N); i++)
#define  Fru(i, n, N)		for (int i = (n); i <  (N); i++)
#define Frde(i, n, N)		for (int i = (n); i >= (N); i--)
#define  Frd(i, n, N)		for (int i = (n); i >  (N); i--)

// PBDS
template<typename Z>
using ordered_set	= tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>;

// Various outputs
template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) {
	return os << '(' << p.fi << ',' << p.se << ')';
}
template<typename Z> ostream& operator<<(ostream &os, const vector<Z> &v) {
	os << '{'; bool _first = 1;
	for (auto &i : v) {if (!_first) os << ", "; os << i; _first = 0;}
	return os << '}';
}
template<typename Z, unsigned long long sz> ostream& operator<<(ostream &os, const array<Z, sz> &arr) {
	os << '{'; bool _first = 1;
	for (auto &i : arr) {if (!_first) os << ", "; os << i; _first = 0;}
	return os << '}';
}

// Quick macro functions
#define sqr(x)			((x)*(x))
#define debug(x)		cout << #x << " = " << (x) << '\n'
#define debugV(v, x)	cout << #v << "[" << (x) << "] = " << (v[x]) << '\n'
#define rrebug(x)		cerr << #x << " = " << (x) << '\n'
#define rrebugV(v, x)	cerr << #v << "[" << (x) << "] = " << (v[x]) << '\n'

#define All(x)			x.begin(), x.end()
#define Sort(x)			sort(All(x))
#define Reverse(x)		reverse(All(x))
#define Uniqueify(x)	Sort(x); x.erase(unique(All(x)), x.end())

#define RandomSeed			chrono::steady_clock::now().time_since_epoch().count()
#define MultipleTestcases	int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++)

// Check min and max
template<typename Z> void chmin(Z &a, Z b) {a = min(a, b);}
template<typename Z> void chmax(Z &a, Z b) {a = max(a, b);}
 
// Modular arithmetic
template<int MOD>
class ModInt {
  public:
	int v;
	ModInt() : v(0) {}
	ModInt(long long _v) {
		v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
		if (v < 0) v += MOD;
	}
 
	friend bool operator==(const ModInt &a, const ModInt &b) {return a.v == b.v;}
	friend bool operator!=(const ModInt &a, const ModInt &b) {return a.v != b.v;}
	friend bool operator< (const ModInt &a, const ModInt &b) {return a.v <  b.v;}
	friend bool operator<=(const ModInt &a, const ModInt &b) {return a.v <= b.v;}
	friend bool operator> (const ModInt &a, const ModInt &b) {return a.v >  b.v;}
	friend bool operator>=(const ModInt &a, const ModInt &b) {return a.v >= b.v;}
 
	ModInt &operator+=(const ModInt &a) {if ((v += a.v) >= MOD) v -= MOD; return *this;}
	ModInt &operator-=(const ModInt &a) {if ((v -= a.v) < 0) v += MOD; return *this;}
	ModInt &operator*=(const ModInt &a) {v = 1ll * v * a.v % MOD; return *this;}
	ModInt &operator/=(const ModInt &a) {return (*this) *= inverse(a);}
 
	friend ModInt pow(ModInt a, long long x) {
		ModInt res = 1;
		for (; x; x /= 2, a *= a) if (x & 1) res *= a;
		return res;
	}
	friend ModInt inverse(ModInt a) {return pow(a, MOD - 2);}
 
	ModInt operator+ () const {return ModInt( v);}
	ModInt operator- () const {return ModInt(-v);}
	ModInt operator++() const {return *this += 1;}
	ModInt operator--() const {return *this -= 1;}
 
	friend ModInt operator+(ModInt a, const ModInt &b) {return a += b;}
	friend ModInt operator-(ModInt a, const ModInt &b) {return a -= b;}
	friend ModInt operator*(ModInt a, const ModInt &b) {return a *= b;}
	friend ModInt operator/(ModInt a, const ModInt &b) {return a /= b;}
 
	friend istream &operator>>(istream &is, ModInt &v) {return is >> v.v;}
	friend ostream &operator<<(ostream &os, const ModInt &v) {return os << v.v;}
};
const int ModA	= 998244353;
const int ModC	= 1e9 + 7;
using MintA	= ModInt<ModA>;
using MintC	= ModInt<ModC>;

// Other constants
const ll INF	= 1e18;
const ll iINF	= 1e9;
const ld EPS	= 1e-9;
const ld iEPS	= 1e-6;

const int maxN	= 105;
const int maxL	= 1005;
const int maxLr	= 1000;

ll N, L, A[maxN];
MintC dp[maxN][maxN][maxL][3];

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

	cin >> N >> L;
	Frue(i, 1, N) cin >> A[i];
	sort(A+1, A+N+1);

	if (N == 1) {
		cout << "1\n";
		return 0;
	}

	dp[0][0][0][0] = 1;
	Fru(i, 0, N) Fru(cc, 0, N) Frue(l, 0, L) Frue(e, 0, 2) {
		MintC cur = dp[i][cc][l][e];
		if (cur == 0) continue;

		ll nl = l + 1ll * (2ll * cc - e) * (A[i+1] - A[i]);
		if (nl < 0 || nl > L) continue;

		// New CC
		{
			// Normal CC
			dp[i+1][cc+1][nl][e] += cur;

			// Edge CC
			if (e < 2) {
				dp[i+1][cc+1][nl][e+1] += MintC(2 - e) * cur;
			}
		}

		// Merge 2 CCs
		{
			// Normal-Normal
			if (cc >= 1 && cc - e >= 2) {
				dp[i+1][cc-1][nl][e] += MintC(cc - e) * MintC(cc - e - 1) * cur;
			}

			// Normal-Edge
			if (cc >= 1 && e >= 1 && cc - e >= 1) {
				dp[i+1][cc-1][nl][e] += MintC(cc - e) * MintC(e) * cur;
			}

			// Edge-Edge
			if (cc == 2 && e == 2 && i == N-1) {
				dp[i+1][cc-1][nl][e] += cur;
			}
		}

		// Stick
		{
			// Stick as Normal
			if (cc > 0) {
				dp[i+1][cc][nl][e] += (MintC(2 * cc) - MintC(e)) * cur;
			}

			// Stick as Edge to Normal
			if (cc > 0 && e < 2) {
				dp[i+1][cc][nl][e+1] += MintC(2 - e) * MintC(cc - e) * cur;
			}

			// Stick as Edge ot Edge
			if (cc == 1 && e == 1 && i == N-1) {
				dp[i+1][cc][nl][e+1] += cur;
			}
		}
	}

	// Fru(i, 0, N) {
	// 	Fru(cc, 0, N) Frue(l, 0, L) Frue(e, 0, 2) {
	// 		if (dp[i][cc][l][e] == 0) continue;
	// 		cout << "dp[" << i << "][" << cc << "][" << l << "][" << e << "] = " << dp[i][cc][l][e] << '\n';
	// 	}
	// 	cout << '\n';
	// }

	MintC ans = 0;
	Frue(l, 0, L) ans += dp[N][1][l][2];
	cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 130380 KB Output is correct
2 Correct 68 ms 130400 KB Output is correct
3 Correct 61 ms 130384 KB Output is correct
4 Correct 64 ms 130376 KB Output is correct
5 Correct 70 ms 130332 KB Output is correct
6 Correct 60 ms 130320 KB Output is correct
7 Correct 60 ms 130292 KB Output is correct
8 Correct 62 ms 130380 KB Output is correct
9 Correct 66 ms 130404 KB Output is correct
10 Correct 64 ms 130340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 130356 KB Output is correct
2 Correct 62 ms 130392 KB Output is correct
3 Correct 58 ms 130332 KB Output is correct
4 Correct 58 ms 130392 KB Output is correct
5 Correct 70 ms 130380 KB Output is correct
6 Correct 69 ms 130388 KB Output is correct
7 Correct 57 ms 130284 KB Output is correct
8 Correct 72 ms 130364 KB Output is correct
9 Correct 64 ms 130384 KB Output is correct
10 Correct 67 ms 130344 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 130380 KB Output is correct
2 Correct 68 ms 130400 KB Output is correct
3 Correct 61 ms 130384 KB Output is correct
4 Correct 64 ms 130376 KB Output is correct
5 Correct 70 ms 130332 KB Output is correct
6 Correct 60 ms 130320 KB Output is correct
7 Correct 60 ms 130292 KB Output is correct
8 Correct 62 ms 130380 KB Output is correct
9 Correct 66 ms 130404 KB Output is correct
10 Correct 64 ms 130340 KB Output is correct
11 Correct 64 ms 130356 KB Output is correct
12 Correct 62 ms 130392 KB Output is correct
13 Correct 58 ms 130332 KB Output is correct
14 Correct 58 ms 130392 KB Output is correct
15 Correct 70 ms 130380 KB Output is correct
16 Correct 69 ms 130388 KB Output is correct
17 Correct 57 ms 130284 KB Output is correct
18 Correct 72 ms 130364 KB Output is correct
19 Correct 64 ms 130384 KB Output is correct
20 Correct 67 ms 130344 KB Output is correct
21 Correct 62 ms 130388 KB Output is correct
22 Correct 127 ms 130404 KB Output is correct
23 Correct 117 ms 130444 KB Output is correct
24 Correct 103 ms 130400 KB Output is correct
25 Correct 108 ms 130292 KB Output is correct
26 Correct 106 ms 130404 KB Output is correct
27 Correct 82 ms 130312 KB Output is correct
28 Correct 85 ms 130368 KB Output is correct
29 Correct 104 ms 130296 KB Output is correct
30 Correct 102 ms 130400 KB Output is correct