Submission #316583

#	Time	Username	Problem	Language	Result	Execution time	Memory
316583		hoaphat1	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	371 ms	90232 KiB

skyscraper

#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 (stderr)

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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80