oj.uz

Submission #646867

# Submission time Handle Problem Language Result Execution time Memory
646867 2022-09-30T21:59:03 Z GusterGoose27 Skyscraper (JOI16_skyscraper) C++11
100 / 100
 211 ms 67996 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 3 ms 2516 KB Output is correct
22 Correct 151 ms 45472 KB Output is correct
23 Correct 203 ms 63044 KB Output is correct
24 Correct 174 ms 59168 KB Output is correct
25 Correct 211 ms 67812 KB Output is correct
26 Correct 177 ms 58240 KB Output is correct
27 Correct 65 ms 28008 KB Output is correct
28 Correct 82 ms 32452 KB Output is correct
29 Correct 148 ms 51664 KB Output is correct
30 Correct 205 ms 67996 KB Output is correct