Submission #606260

#	Time	Username	Problem	Language	Result	Execution time	Memory
606260		TranGiaHuy1508	Skyscraper (JOI16_skyscraper)	C++17	0 / 100	6 ms	3288 KiB

skyscraper

/*
	Unknown's C++ Template (v3.2)
*/

#include "bits/stdc++.h"
using namespace std;

#define int long long

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
template <class T> using maxpq = priority_queue<T>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mid ((l+r)>>1)
#define fi first
#define se second

#ifdef LOCAL
	#define debug(x) cout << #x << " = " << x << "\n";
#else
	#define debug(x) ;
#endif

template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x)
{ out << "(" << x.first << ", " << x.second << ")"; return out; }

template <class T>
ostream& operator << (ostream& out, vector<T> x){
	out << "[";
	for (int i=0; i<sz(x); i++) { out << (i ? ", " : "") << x[i]; }
	out << "]"; return out;
}

template <class T>
istream& operator >> (istream& in, vector<T> &x){
	for (auto &i: x) in >> i;
	return in;
}

const ld PI = acos(-1.0);
const int allmod[3] = {(int)1e9+7, 998244353, (int)1e9+9};
const int mod = allmod[0];
const int maxn = 1e2 + 5;
const ll inf = 1e18;
const ld eps = 1e-6;
const int multitest = 0;

map<int, int> dp[maxn][maxn][2][2];
// dp[blocks][middle_gaps][gap_left][gap_right] = {sum_of_diff: ways}

void add(int &a, int b){
	a = (a + b) % mod;
}

void main_program(){
	int n, l; cin >> n >> l;
	vi v(n); cin >> v;
	sort(all(v));

	dp[0][0][1][1][-2 * v[0]] = 1;
	dp[0][0][0][1][-v[0]] = 1;
	dp[0][0][1][0][-v[0]] = 1;
	dp[0][0][0][0][0] = 1;

	for (int i = 1; i < n; i++){
		// +2
		for (int middle_gaps = 1; middle_gaps < maxn; middle_gaps++){
			for (int gap_left = 0; gap_left < 2; gap_left++){
				for (int gap_right = 0; gap_right < 2; gap_right++){
					for (auto [diff, ways]: dp[i-1][middle_gaps][gap_left][gap_right]){
						add(dp[i][middle_gaps-1][gap_left][gap_right][diff + 2 * v[i]], middle_gaps * ways);
					}
				}
			}
		}
		// +1
		for (int middle_gaps = 0; middle_gaps < maxn; middle_gaps++){
			// left
			for (int gap_right = 0; gap_right < 2; gap_right++){
				for (auto [diff, ways]: dp[i-1][middle_gaps][1][gap_right]){
					add(dp[i][middle_gaps][0][gap_right][diff + v[i]], ways); 
				}
			}
			// right
			for (int gap_left = 0; gap_left < 2; gap_left++){
				for (auto [diff, ways]: dp[i-1][middle_gaps][gap_left][1]){
					add(dp[i][middle_gaps][gap_left][0][diff + v[i]], ways);
				}
			}
		}
		// 0
		for (int middle_gaps = 0; middle_gaps < maxn; middle_gaps++){
			for (int gap_left = 0; gap_left < 2; gap_left++){
				for (int gap_right = 0; gap_right < 2; gap_right++){
					for (auto [diff, ways]: dp[i-1][middle_gaps][gap_left][gap_right]){
						add(dp[i][middle_gaps][gap_left][gap_right][diff], middle_gaps * 2 * ways);
					}
				}
			}
		}
		// -1
		for (int middle_gaps = 0; middle_gaps < maxn; middle_gaps++){
			// left
			for (int gap_right = 0; gap_right < 2; gap_right++){
				for (auto [diff, ways]: dp[i-1][middle_gaps][1][gap_right]){
					add(dp[i][middle_gaps][1][gap_right][diff - v[i]], ways); 
				}
			}
			// right
			for (int gap_left = 0; gap_left < 2; gap_left++){
				for (auto [diff, ways]: dp[i-1][middle_gaps][gap_left][1]){
					add(dp[i][middle_gaps][gap_left][1][diff - v[i]], ways);
				}
			}
		}
		// -2
		for (int middle_gaps = 0; middle_gaps < maxn - 1; middle_gaps++){
			for (int gap_left = 0; gap_left < 2; gap_left++){
				for (int gap_right = 0; gap_right < 2; gap_right++){
					for (auto [diff, ways]: dp[i-1][middle_gaps][gap_left][gap_right]){
						add(dp[i][middle_gaps+1][gap_left][gap_right][diff - 2 * v[i]], middle_gaps * ways);
					}
				}
			}
		}
	}

	int s = 0;
	for (int i = 0; i <= l; i++) add(s, dp[n-1][0][0][0][i]);
	cout << (s + mod) % mod << "\n";
}

void pre_main(){

}

signed main(){
	#ifdef LOCAL
		auto stime = chrono::high_resolution_clock::now();
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#ifndef ONLINE_JUDGE
		if (fopen(".inp", "r")){
			freopen(".inp", "r", stdin);
			freopen(".out", "w", stdout);
		}
	#endif
	int t = 1; if (multitest) cin >> t;
	pre_main();
	while (t--) main_program();
	#ifdef LOCAL
		auto etime = chrono::high_resolution_clock::now();
		auto duration = chrono::duration_cast<chrono::milliseconds>(etime-stime).count();
		cout << "\n[" << duration << "ms]\n";
	#endif
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:154:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |    freopen(".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:155:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |    freopen(".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 80