Submission #646867

#	Time	Username	Problem	Language	Result	Execution time	Memory
646867		GusterGoose27	Skyscraper (JOI16_skyscraper)	C++11	100 / 100	211 ms	67996 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MAXN = 101;
const ll MAXL = 2001;
const ll MOD = 1e9+7;
ll n, l;
ll heights[MAXN];
ll dp[MAXN][MAXN][MAXL][2][2]; // number of elems, number of cc, value if all other things are next value, left occupied, right occupied
#define fin cin

void gen_case() {
	set<int> chosen;
	srand(time(0));
	ofstream fout("skyscraper.in");
	int curn = 8;
	int curl = 1000;
	fout << curn << " " << curl << "\n";
	for (int i = 0; i < curn; i++) {
		int v;
		do v = rand() % 1001;
		while (chosen.find(v) != chosen.end());
		chosen.insert(v);
		if (i) fout << " ";
		fout << v;
	}
	fout << endl;
	fout.close();
}

/*
Transitions:

We can create a new cc, add to an existing one, or merge two

New cc:
	Rescale all cc boundaries to the next increment
	open spaces = cc-1
	current value = 2*next-cur elem
	this could go in any of the open spaces

*/

void dpa(ll &a, ll &b) {
	a += b;
	a %= MOD;
}

// void dpa(ll &a, ll &b) {
// 	a += b;
// 	a %= MOD;
// }

bool valid(vector<int> &v) {
	int s = 0;
	for (int i = 0; i < v.size()-1; i++) s += abs(heights[v[i+1]-1]-heights[v[i]-1]);
	return (s <= l);
}

int bash() {
	vector<int> v(n);
	iota(v.begin(), v.end(), 1);
	bool worked = 1;
	int ans = 0;
	while (worked) {
		if (valid(v)) ans++;
		worked = next_permutation(v.begin(), v.end());
	}
	return ans;
}

int solve() {
	//memset(dp, 0, sizeof(dp));
	//ifstream fin("skyscraper.in");
	ios_base::sync_with_stdio(false); fin.tie(NULL);
	fin >> n >> l;
	for (ll i = 0; i < n; i++) fin >> heights[i];
	sort(heights, heights+n);
	if (n == 1) {
		return 1;
	}
	ll curv = 2*(heights[1]-heights[0]);;
	if (curv <= l) dp[1][1][curv][0][0] = 1;
	curv += heights[0]-heights[1];
	if (curv <= l) {
		dp[1][1][curv][1][0] = 1;
		dp[1][1][curv][0][1] = 1;
	}
	heights[n] = heights[n-1];
	for (ll i = 2; i <= n; i++) {
		for (ll j = 1; j <= min(i, n+1-i); j++) {
			for (ll v = 0; v <= l; v++) {
				for (ll lo = 0; lo < 2; lo++) {
					for (ll ro = 0; ro < 2; ro++) {
						if (j > 1) {
							ll bounds = 2*(j-1)-lo-ro;
							ll ex = (heights[i]-heights[i-1])*bounds+2*heights[i]-2*heights[i-1];
							if (ex <= v) {
								ll cur = (ll) (j-lo-ro)*dp[i-1][j-1][v-ex][lo][ro];
								cur %= MOD;
								dpa(dp[i][j][v][lo][ro], cur);
							}
							ll nex = ex;
							if (nex <= v) {
								if (lo) dpa(dp[i][j][v][lo][ro], dp[i-1][j-1][v-nex][0][ro]);
								if (ro) dpa(dp[i][j][v][lo][ro], dp[i-1][j-1][v-nex][lo][0]);
							}
						}
						ll bounds = 2*j-lo-ro;
						ll ex = (heights[i]-heights[i-1])*bounds;
						if (ex <= v) {
							ll cur = (ll) (2*j-lo-ro)*dp[i-1][j][v-ex][lo][ro];
							cur %= MOD;
							dpa(dp[i][j][v][lo][ro], cur);
						}
						ll nex = ex;
						if (nex <= v) {
							if (lo) dpa(dp[i][j][v][lo][ro], dp[i-1][j][v-nex][0][ro]);
							if (ro) dpa(dp[i][j][v][lo][ro], dp[i-1][j][v-nex][lo][0]);
						}
						bounds = 2*j-lo-ro;
						ex = (heights[i]-heights[i-1])*bounds;
						if (ex <= v) {
							ll cur = (ll) (j)*dp[i-1][j+1][v-ex][lo][ro];
							cur %= MOD;
							dpa(dp[i][j][v][lo][ro], cur);
						}
					}
				}
			}
		}
	}
	ll ans = 0;
	for (ll i = 0; i <= l; i++) {
		dpa(ans, dp[n][1][i][1][1]);
	}
	//fin.close();
	return ans;
}

int main() {
	int s = solve();
	//int b = bash();
	//assert(s == b);
	//cout << b << "\n";
	cout << s << "\n";
	return 0;
	while (1) {
		gen_case();
		int s = solve();
		int b = bash();
		if (s != b) {
			cerr << s << " " << b << endl;
		}
		assert(s == b);
	}
}

Compilation message (stderr)

skyscraper.cpp: In function 'bool valid(std::vector<int>&)':
skyscraper.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < v.size()-1; i++) s += abs(heights[v[i+1]-1]-heights[v[i]-1]);
      |                  ~~^~~~~~~~~~~~

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