oj.uz

Submission #606376

# Submission time Handle Problem Language Result Execution time Memory
606376 2022-07-26T06:31:19 Z TranGiaHuy1508 Skyscraper (JOI16_skyscraper) C++17
20 / 100
 2000 ms 190596 KB 
/*
	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;
// }

#define add(a, b) ((a) = (a) + (b))

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]], 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][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], middle_gaps * 2 * ways);
						// 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);
				}
			}
		}
	}

	int 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
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct
3 Correct 2 ms 2388 KB Output is correct
4 Correct 2 ms 2444 KB Output is correct
5 Correct 11 ms 4180 KB Output is correct
6 Correct 11 ms 4340 KB Output is correct
7 Correct 7 ms 3412 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 11 ms 4308 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2900 KB Output is correct
2 Correct 59 ms 9088 KB Output is correct
3 Correct 11 ms 3756 KB Output is correct
4 Correct 52 ms 9192 KB Output is correct
5 Correct 65 ms 10652 KB Output is correct
6 Correct 31 ms 6480 KB Output is correct
7 Correct 21 ms 4820 KB Output is correct
8 Correct 10 ms 3672 KB Output is correct
9 Correct 11 ms 3796 KB Output is correct
10 Correct 41 ms 7808 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct
3 Correct 2 ms 2388 KB Output is correct
4 Correct 2 ms 2444 KB Output is correct
5 Correct 11 ms 4180 KB Output is correct
6 Correct 11 ms 4340 KB Output is correct
7 Correct 7 ms 3412 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 11 ms 4308 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 7 ms 2900 KB Output is correct
12 Correct 59 ms 9088 KB Output is correct
13 Correct 11 ms 3756 KB Output is correct
14 Correct 52 ms 9192 KB Output is correct
15 Correct 65 ms 10652 KB Output is correct
16 Correct 31 ms 6480 KB Output is correct
17 Correct 21 ms 4820 KB Output is correct
18 Correct 10 ms 3672 KB Output is correct
19 Correct 11 ms 3796 KB Output is correct
20 Correct 41 ms 7808 KB Output is correct
21 Correct 756 ms 74216 KB Output is correct
22 Execution timed out 2072 ms 190596 KB Time limit exceeded
23 Halted 0 ms 0 KB -