oj.uz

Submission #332737

# Submission time Handle Problem Language Result Execution time Memory
332737 2020-12-03T05:37:14 Z Kevin_Zhang_TW Skyscraper (JOI16_skyscraper) C++17
100 / 100
 1733 ms 11884 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &v, T val) { return v < val ? (v = val, true) : false; }
template<class T>
bool chmin(T &v, T val) { return val < v ? (v = val, true) : false; }

#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U>
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_L = 1005, p = 1e9+7, MAX_N = 105, MAX_K = 3;
int n, L, a[MAX_N], cnt[MAX_N];
int dp[3][3][MAX_N][MAX_N][MAX_L], tmp[3][3][MAX_N][MAX_N][MAX_L];
void add(int &v, int val) { v = (v + val) % p; return; v += val - p, v += (v>>31) & p; }
void add(ll &v, int val) {  v = (v + val) % p; return; v += val - p, v += (v>>63) & p; }
ll C(ll a, ll b) { assert(b == 2); return (a * (a-1) / 2); }
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> L;
	for (int i = 1;i <= n;++i) {
		cin >> a[i];
	}
	sort(a+1, a+n+1);

	if (n == 1) return puts("1"), 0;

	auto dp = ::dp;
	auto tmp = ::tmp;
// dp[d][a][b][c][cost]
	dp[0][0][0][0][0] = 2;
	for (int i = 0;i <= n;++i) {
		int gap = a[i+1] - a[i];
		DE(i, gap);
		for (int d = 0;d <= 2;++d)
			for (int a = 0;a <= 2;++a) 
				for (int b = 0;b <= i;++b) for (int c = 0;c + a + b <= i;++c) {
					for (int cost = 0;cost <= L;++cost) if (dp[d][a][b][c][cost]) {
						ll now = dp[d][a][b][c][cost];
						dp[d][a][b][c][cost] = 0;
						ll nc = cost + (a + (b + c) * 2) * gap;
						DE(d,a,b,c,cost,now);
						if (i == n) {
							tmp[d][a][b][c][cost] = now;
							continue;
						}
						if (nc > L) continue;
						// if deg == 1
						if (d < 2) {
							// if point back
							// to c
							if (c) 
								add(tmp[d + 1][a + 1][b][c - 1][nc], now * 2 * c % p);
							// to b
							if (b)
								add(tmp[d + 1][a + 1][b - 1][c][nc], now * b % p);
							// to a
							if (a && b == 0 && c == 0)
								add(tmp[d + 1][a - 1][b][c][nc], now * a % p);
							// if point forward
							add(tmp[d + 1][a + 1][b][c][nc], now);
						}
						// if deg == 2
						if (a && b)
							add(tmp[d][a][b - 1][c][nc], now * a * b % p);
						if (a && c)
							add(tmp[d][a][b][c - 1][nc], now * a * c * 2 % p);
						if (b && c)
							add(tmp[d][a][b - 1][c][nc], now * b * c * 2 % p);
						// self to aa, bb, cc
						if (a >= 2)
							add(tmp[d][a - 2][b][c][nc], now);
						if (b >= 2)
							add(tmp[d][a][b - 2][c + 1][nc], now * C(b, 2) % p);
						if (c >= 2)
							add(tmp[d][a][b][c - 1][nc], now * C(c, 2) * 4 % p);
						// self be b
						add(tmp[d][a][b + 1][c][nc], now);
						// self to a, b, c
						if (a)
							add(tmp[d][a][b][c][nc], now * a % p);
						if (b)
							add(tmp[d][a][b - 1][c + 1][nc], now * b % p);
						if (c)
							add(tmp[d][a][b][c][nc], now * c * 2 % p);
					}
				}
		swap(dp, tmp);
	}
	cout << accumulate(dp[2][0][0][0], dp[2][0][0][0] + L + 1, 0ll) % p << '\n';
}

Compilation message

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:19:17: warning: statement has no effect [-Wunused-value]
   19 | #define DE(...) 0
      |                 ^
skyscraper.cpp:45:3: note: in expansion of macro 'DE'
   45 |   DE(i, gap);
      |   ^~
skyscraper.cpp:19:17: warning: statement has no effect [-Wunused-value]
   19 | #define DE(...) 0
      |                 ^
skyscraper.cpp:53:7: note: in expansion of macro 'DE'
   53 |       DE(d,a,b,c,cost,now);
      |       ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 748 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 1 ms 876 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1516 KB Output is correct
2 Correct 3 ms 1004 KB Output is correct
3 Correct 3 ms 1132 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 3 ms 1004 KB Output is correct
6 Correct 3 ms 1004 KB Output is correct
7 Correct 2 ms 876 KB Output is correct
8 Correct 3 ms 1132 KB Output is correct
9 Correct 3 ms 1388 KB Output is correct
10 Correct 3 ms 1004 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 748 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 3 ms 1516 KB Output is correct
12 Correct 3 ms 1004 KB Output is correct
13 Correct 3 ms 1132 KB Output is correct
14 Correct 3 ms 876 KB Output is correct
15 Correct 3 ms 1004 KB Output is correct
16 Correct 3 ms 1004 KB Output is correct
17 Correct 2 ms 876 KB Output is correct
18 Correct 3 ms 1132 KB Output is correct
19 Correct 3 ms 1388 KB Output is correct
20 Correct 3 ms 1004 KB Output is correct
21 Correct 18 ms 1556 KB Output is correct
22 Correct 1588 ms 11884 KB Output is correct
23 Correct 1661 ms 4024 KB Output is correct
24 Correct 1393 ms 4432 KB Output is correct
25 Correct 1733 ms 3848 KB Output is correct
26 Correct 1449 ms 3692 KB Output is correct
27 Correct 585 ms 5228 KB Output is correct
28 Correct 740 ms 5996 KB Output is correct
29 Correct 1300 ms 6380 KB Output is correct
30 Correct 1702 ms 3692 KB Output is correct