oj.uz

Submission #316583

# Submission time Handle Problem Language Result Execution time Memory
316583 2020-10-26T18:13:11 Z hoaphat1 Skyscraper (JOI16_skyscraper) C++17
100 / 100
 371 ms 90232 KB 
#include<bits/stdc++.h>

using namespace std;

/// from tourist
template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int N = 105;
const int md = (int)1e9 + 7;

int n,mx;
int a[N];
int dp[N][N / 2][2][2][N * 10];

void add(int&a,const int &b) {
	if ((a += b) >= md) a -= md;
}

int mul(const int&a,const int&b) {
	return 1ll * a * b % md;
}

int f(int pos,int num,bool L,bool R,int diff) {
	if (pos) {
		diff += a[pos - 1] * (2 * num - L - R);
	}
	if (diff > mx) return 0;
	int& res = dp[pos][num][L][R][diff];
	if (res != -1) return res;
	if (pos == n) {
		if (L && R && num == 1) return 1;
		return 0;
	}
	res = 0;
	// create new comp except L,R
	add(res,mul(f(pos + 1,num + 1,L,R,diff) , num + 1 - L - R));
	// create new L,R
	if (!L) add(res,f(pos + 1,num + 1,1,R,diff));
	if (!R) add(res,f(pos + 1,num + 1,L,1,diff));
	if (num) {
		// push_front
		add(res,mul(f(pos + 1,num,L,R,diff) , num - L));
		// push_back 
		add(res,mul(f(pos + 1,num,L,R,diff) , num - R));
		// connect
		if (num > 1) add(res,mul(f(pos + 1,num - 1,L,R,diff) , num - 1));
		// push L,R
		if (!L) add(res,f(pos + 1,num,1,R,diff));
		if (!R) add(res,f(pos + 1,num,L,1,diff));
	}
	debug(pos,num,L,R,diff,res);
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> mx;
	if (n == 1) return cout << 1,0;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a,a + n);
	for (int i = 1; i <= n; i++) a[i-1] = a[i] - a[i-1];
	memset(dp,-1,sizeof dp);
	cout << f(0,0,0,0,0);
}

Compilation message

skyscraper.cpp: In function 'int f(int, int, bool, bool, int)':
skyscraper.cpp:91:20: warning: statement has no effect [-Wunused-value]
   91 | #define debug(...) 42
      |                    ^~
skyscraper.cpp:137:2: note: in expansion of macro 'debug'
  137 |  debug(pos,num,L,R,diff,res);
      |  ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 53 ms 90104 KB Output is correct
3 Correct 52 ms 90104 KB Output is correct
4 Correct 52 ms 90104 KB Output is correct
5 Correct 54 ms 90104 KB Output is correct
6 Correct 53 ms 90104 KB Output is correct
7 Correct 52 ms 90108 KB Output is correct
8 Correct 52 ms 90104 KB Output is correct
9 Correct 53 ms 90112 KB Output is correct
10 Correct 52 ms 90104 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 90104 KB Output is correct
2 Correct 53 ms 90108 KB Output is correct
3 Correct 53 ms 90104 KB Output is correct
4 Correct 53 ms 90104 KB Output is correct
5 Correct 53 ms 90136 KB Output is correct
6 Correct 53 ms 90104 KB Output is correct
7 Correct 53 ms 90104 KB Output is correct
8 Correct 54 ms 90104 KB Output is correct
9 Correct 53 ms 90112 KB Output is correct
10 Correct 54 ms 90104 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 53 ms 90104 KB Output is correct
3 Correct 52 ms 90104 KB Output is correct
4 Correct 52 ms 90104 KB Output is correct
5 Correct 54 ms 90104 KB Output is correct
6 Correct 53 ms 90104 KB Output is correct
7 Correct 52 ms 90108 KB Output is correct
8 Correct 52 ms 90104 KB Output is correct
9 Correct 53 ms 90112 KB Output is correct
10 Correct 52 ms 90104 KB Output is correct
11 Correct 53 ms 90104 KB Output is correct
12 Correct 53 ms 90108 KB Output is correct
13 Correct 53 ms 90104 KB Output is correct
14 Correct 53 ms 90104 KB Output is correct
15 Correct 53 ms 90136 KB Output is correct
16 Correct 53 ms 90104 KB Output is correct
17 Correct 53 ms 90104 KB Output is correct
18 Correct 54 ms 90104 KB Output is correct
19 Correct 53 ms 90112 KB Output is correct
20 Correct 54 ms 90104 KB Output is correct
21 Correct 53 ms 90104 KB Output is correct
22 Correct 371 ms 90232 KB Output is correct
23 Correct 138 ms 90232 KB Output is correct
24 Correct 178 ms 90104 KB Output is correct
25 Correct 150 ms 90104 KB Output is correct
26 Correct 137 ms 90232 KB Output is correct
27 Correct 117 ms 90104 KB Output is correct
28 Correct 147 ms 90104 KB Output is correct
29 Correct 244 ms 90140 KB Output is correct
30 Correct 150 ms 90164 KB Output is correct