oj.uz

답안 #51679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51679 2018-06-19T23:14:26 Z shoemakerjo Skyscraper (JOI16_skyscraper) C++14
100 / 100
 521 ms 165400 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 127 ms 164980 KB Output is correct
3 Correct 128 ms 165076 KB Output is correct
4 Correct 130 ms 165096 KB Output is correct
5 Correct 126 ms 165240 KB Output is correct
6 Correct 129 ms 165240 KB Output is correct
7 Correct 132 ms 165240 KB Output is correct
8 Correct 152 ms 165240 KB Output is correct
9 Correct 129 ms 165240 KB Output is correct
10 Correct 126 ms 165240 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 165240 KB Output is correct
2 Correct 133 ms 165240 KB Output is correct
3 Correct 162 ms 165240 KB Output is correct
4 Correct 128 ms 165280 KB Output is correct
5 Correct 127 ms 165288 KB Output is correct
6 Correct 128 ms 165288 KB Output is correct
7 Correct 129 ms 165288 KB Output is correct
8 Correct 128 ms 165288 KB Output is correct
9 Correct 141 ms 165288 KB Output is correct
10 Correct 135 ms 165288 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 127 ms 164980 KB Output is correct
3 Correct 128 ms 165076 KB Output is correct
4 Correct 130 ms 165096 KB Output is correct
5 Correct 126 ms 165240 KB Output is correct
6 Correct 129 ms 165240 KB Output is correct
7 Correct 132 ms 165240 KB Output is correct
8 Correct 152 ms 165240 KB Output is correct
9 Correct 129 ms 165240 KB Output is correct
10 Correct 126 ms 165240 KB Output is correct
11 Correct 133 ms 165240 KB Output is correct
12 Correct 133 ms 165240 KB Output is correct
13 Correct 162 ms 165240 KB Output is correct
14 Correct 128 ms 165280 KB Output is correct
15 Correct 127 ms 165288 KB Output is correct
16 Correct 128 ms 165288 KB Output is correct
17 Correct 129 ms 165288 KB Output is correct
18 Correct 128 ms 165288 KB Output is correct
19 Correct 141 ms 165288 KB Output is correct
20 Correct 135 ms 165288 KB Output is correct
21 Correct 135 ms 165288 KB Output is correct
22 Correct 521 ms 165288 KB Output is correct
23 Correct 229 ms 165288 KB Output is correct
24 Correct 269 ms 165288 KB Output is correct
25 Correct 298 ms 165288 KB Output is correct
26 Correct 290 ms 165288 KB Output is correct
27 Correct 213 ms 165352 KB Output is correct
28 Correct 267 ms 165352 KB Output is correct
29 Correct 342 ms 165400 KB Output is correct
30 Correct 267 ms 165400 KB Output is correct