제출 #606463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
606463		TranGiaHuy1508	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	2081 ms	171708 KiB

skyscraper

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

#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx,avx2,fma,bmi,bmi2,sse4.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, ll> 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;
// }

#define add(a, 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++){
			// middle
			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]], ways * middle_gaps);
						// if (dp[i][middle_gaps-1][gap_left][gap_right][diff + 2 * v[i]] > 0){
						// 	cout << "dp[" << i << "][" << middle_gaps-1 << "][" << gap_left << "][" << gap_right << "][" << diff + 2 * v[i] << "] = " << dp[i][middle_gaps-1][gap_left][gap_right][diff + 2 * v[i]] << "\n";
						// 	debug(i); debug(middle_gaps); debug(gap_left); debug(gap_right); debug(diff); debug(ways);
						// 	debug("+2");
						// }
					}
				}
			}
			// // 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 + 2 * 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 + 2 * v[i]], 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);
					// if (dp[i][middle_gaps][0][gap_right][diff + v[i]] > 0){
					// 	cout << "dp[" << i << "][" << middle_gaps << "][" << 0 << "][" << gap_right << "][" << diff + v[i] << "] = " << dp[i][middle_gaps][0][gap_right][diff + v[i]] << "\n";
					// 	debug(i); debug(middle_gaps); debug(0); debug(gap_right); debug(diff); debug(ways);
					// 	debug("+1 left");
					// }
				}
			}
			// 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);
					// if (dp[i][middle_gaps][gap_left][0][diff + v[i]] > 0){
					// 	cout << "dp[" << i << "][" << middle_gaps << "][" << gap_left << "][" << 0 << "][" << diff + v[i] << "] = " << dp[i][middle_gaps][gap_left][0][diff + v[i]] << "\n";
					// 	debug(i); debug(middle_gaps); debug(gap_left); debug(0); debug(diff); debug(ways);
					// 	debug("+1 right");
					// }
				}
			}
		}
		// 0
		for (int middle_gaps = 0; middle_gaps < maxn; middle_gaps++){
			// middle
			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], ways * middle_gaps * 2);
						// if (dp[i][middle_gaps][gap_left][gap_right][diff] > 0){
						// 	cout << "dp[" << i << "][" << middle_gaps << "][" << gap_left << "][" << gap_right << "][" << diff << "] = " << dp[i][middle_gaps][gap_left][gap_right][diff] << "\n";
						// 	debug(i); debug(middle_gaps); debug(gap_left); debug(gap_right); debug(diff); debug(ways);
						// 	debug("0")
						// }
					}
				}
			}
			// 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][0][gap_right][diff], ways);
					add(dp[i][middle_gaps][1][gap_right][diff], 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+1][gap_left][0][diff], ways);
					add(dp[i][middle_gaps][gap_left][1][diff], ways);
				}
			}
		}
		// -1
		for (int middle_gaps = 0; middle_gaps < maxn - 1; 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][0][gap_right][diff - v[i]], ways); 
					// if (dp[i][middle_gaps][1][gap_right][diff - v[i]] > 0){
					// 	cout << "dp[" << i << "][" << middle_gaps << "][" << 1 << "][" << gap_right << "][" << diff - v[i] << "] = " << dp[i][middle_gaps][1][gap_right][diff - v[i]] << "\n";
					// 	debug(i); debug(middle_gaps); debug(1); debug(gap_right); debug(diff); debug(ways);
					// 	debug("-1 left")
					// }
				}
			}
			// 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+1][gap_left][0][diff - v[i]], ways);
					// if (dp[i][middle_gaps][gap_left][1][diff - v[i]] > 0){
					// 	cout << "dp[" << i << "][" << middle_gaps << "][" << gap_left << "][" << 1 << "][" << diff - v[i] << "] = " << dp[i][middle_gaps][gap_left][1][diff - v[i]] << "\n";
					// 	debug(i); debug(middle_gaps); debug(gap_left); debug(1); debug(diff); debug(ways);
					// 	debug("-1 right")
					// }
				}
			}
		}
		// -2
		for (int middle_gaps = 0; middle_gaps < maxn - 1; middle_gaps++){
			// middle
			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);
						// if (dp[i][middle_gaps+1][gap_left][gap_right][diff - 2 * v[i]] > 0){
						// 	cout << "dp[" << i << "][" << middle_gaps+1 << "][" << gap_left << "][" << gap_right << "][" << diff - 2 * v[i] << "] = " << dp[i][middle_gaps+1][gap_left][gap_right][diff - 2 * v[i]] << "\n";
						// 	debug(i); debug(middle_gaps); debug(gap_left); debug(gap_right); debug(diff); debug(ways);
						// 	debug("-2")
						// }
					}
				}
			}
			// 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][1][gap_right][diff - 2 * 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+1][gap_left][1][diff - 2 * v[i]], ways);
				}
			}
		}
	}

	ll s = 0;
	for (int i = 0; i <= l; i++) add(s, dp[n-1][0][0][0][i]);
	// for (int i = 0; i <= l; i++){
	// 	if (dp[n-1][0][0][0][i] > 0){
	// 		cout << i << " " << dp[n-1][0][0][0][i] << "\n";
	// 	}
	// }
	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
}

컴파일 시 표준 에러 (stderr) 메시지

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

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