Submission #51679

#	Time	Username	Problem	Language	Result	Execution time	Memory
51679		shoemakerjo	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	521 ms	165400 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;
const int mod = 1000000007;
#define ll long long
#define maxn 102
#define maxl 1010
int N, L;
int nums[maxn];
int dp[2][2][maxn][maxn][maxl];
//above should be initialized to all zeroes

int mult(ll a, ll b) {
	return (a*b)%mod;
}

//how do i get here
int go(int lflag, int rflag, int ind, int groups, int curl) {

	bool isz = lflag == 0 && rflag == 0 && ind == 0 && groups == 0 && curl == L; //solely for debugging

	//flags for wether left or right are filled
	// the index of the thing we are placing
	// the number of groups that there are
	int numopen = groups + 1; //one on the end
	if (groups < 0) return 0;
	
	if (lflag) numopen--;
	if (rflag) numopen--;
	
	
	// if (numopen == 0) cout << "here: " << ind << endl;

	//every open spot increases by the difference in values because of the increase
	int numdec = numopen*2; //number to decrease
	if (!lflag) numdec--; //don't sub on the left
	if (!rflag) numdec--;
	if (ind > 0) {
		//every open spot was considered before to be nums[ind-1], but now it is considered to be nums[ind]
		curl -= (nums[ind]-nums[ind-1]) * numdec; 
	}

	if (lflag < 0 || lflag > 1) return 0;
	if (rflag < 0 || rflag > 1) return 0;
	if (numopen < 0) return 0; //should not happen
	if (curl < 0) return 0;

	// if (numopen == 0) cout << "here: " << ind << endl;

	if (ind == N) {
		//already placed everything
		// cout << "at N with numopen equal to " << numopen << endl;	

		if (lflag && rflag && numopen == 0) {
			return 1;
		} //nothing should be open at the end
		else return 0; //did not satisfy the correct conditions
	}

	if (dp[lflag][rflag][ind][groups][curl] != -1) {
		return dp[lflag][rflag][ind][groups][curl];
	}

	int res = 0; //this is the result

	//option 1 : add it loosely wherever
	res += mult(numopen, go(lflag, rflag, ind+1, groups+1, curl)); 
	res %= mod;
	//increase the number of groups by 1, you can put it in any of the open portions

	// if (isz) cout << "from option 1: " << res <<  " : " << numopen << endl;

	//option 2 : loosely place me on the left edge (or right edge) - adds a group
	if (!lflag) res += go(lflag+1, rflag, ind+1, groups+1, curl);
	res %= mod;
	if (!rflag) res += go(lflag, rflag+1, ind+1, groups+1, curl);
	res %= mod;

	//option 3 : bind me to one thing (must have a group to do this)
	//    you can actually bind me to either side if I am in the middle
	int numbind = 2*numopen;
	if (!rflag) numbind--;
	if (!lflag) numbind--;
	if (groups >= 1) res += mult(numbind, go(lflag, rflag, ind+1, groups, curl));
	res %= mod;

	//option 4 : bind me to something and put me on the edge (need to have a group for this)
	if (groups >= 1 && !lflag) res += go(lflag+1, rflag, ind+1, groups, curl);
	res %= mod;
	if (groups >= 1 && !rflag) res += go(lflag, rflag+1, ind+1, groups, curl);
	res %= mod;

	//option 5: double bind me (subtracts 1 from the number of groups);
	//must bind be in the middle of two things
	numbind = numopen;
	if (!lflag) numbind--;
	if (!rflag) numbind--;
	if (groups >= 2) res += mult(numbind, go(lflag, rflag, ind+1, groups-1, curl));
	res %= mod;

	return dp[lflag][rflag][ind][groups][curl] = res;

}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> L;
	if (N == 1) {
		cout << 1 << endl;
		return 0; //just in case
	}
	for (int i = 0; i < N; i++) {
		cin >> nums[i];
	}
	sort(nums, nums+N);
	for (int i1 = 0; i1 < 2; i1++) { //set everything to negative one
		for (int i2 = 0; i2 < 2; i2++) {
			for (int i3 = 0; i3 < maxn; i3++) {
				for (int i4 = 0; i4 < maxn; i4++) {
					for (int i5 = 0; i5 < maxl; i5++) {
						dp[i1][i2][i3][i4][i5] = -1;
					}
				}
			}
		}
	}

	int ans = go(0, 0, 0, 0, L); //starting state
	cout << ans << endl;

	//debug below
	// for (int i1 = 0; i1 < 2; i1++) { //set everything to negative one
	// 	for (int i2 = 0; i2 < 2; i2++) {
	// 		for (int i3 = 0; i3 < 4; i3++) {
	// 			for (int i4 = 0; i4 <= 4; i4++) {
	// 				for (int i5 = 0; i5 <= L; i5++) {
	// 					// if (dp[i1][i2][i3][i4][i5] != -1) 
	// 						// cout << i1 << " " << i2 << " "  << i3 << " " << i4 << " " << i5 << ":  " << dp[i1][i2][i3][i4][i5] << endl;
						
	// 				}
	// 			}
	// 		}
	// 	}
	// }

	cin >> ans;
}
//dp state
//number we are one (going to be 0 through N)
//   ---- also dictates how many numbers are added
//number of  things that are loosely placed
//  ----- dictates number of spots
// flags for if either end is set (2 of them)
// current sum of cost (going up to L)

// 2 * 2 * N * N * L = 40,000,000 states

// transitions: 
//     loosely place me (creates two open spots)
//     loosely place me on an edge (creates one open spot)
//     place me on edge and bind me to another guy (subtracts one open)
//     bind me in the middle to one guy (keeps open spots constant)
//     bind two middle guys together
//     bind something on the edge and something in the middle

//issue is with cost recalculation (if loosely placed cost is -2 * my value)
//every time, each open spot is assumed to be just the current value
//when we move up a number, we subtract (nums[i] - nums[i-1]) * # open spots

//transitions are still o(1) but bad
//handle case for n = 1 explicitly (left and right stuff gets weird)

Compilation message (stderr)

skyscraper.cpp: In function 'int go(int, int, int, int, int)':
skyscraper.cpp:20:7: warning: unused variable 'isz' [-Wunused-variable]
  bool isz = lflag == 0 && rflag == 0 && ind == 0 && groups == 0 && curl == L; //solely for debugging
       ^~~

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