oj.uz

답안 #452152

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
452152 2021-08-04T00:02:43 Z gmyu Skyscraper (JOI16_skyscraper) C++14
100 / 100
 98 ms 50788 KB 
/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/JOI16_skyscr
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <string.h>
#include <set>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define ff  first
#define ss  second
#define pb  push_back
#define sz(x)   (int)(x).size()

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 1007
#define MAXE 100007

bool debug;

ll dp[101][101][1001][3];
/**
we sort the values ai and add them into the permutation one by one.
At each point, we will have some connected components of values
(for example it will be something like 2,?,1,5,?,?,3,?,4)
But then, we can freely arrange each block to form all permutations

dp[i][j][k][l] : number of ways when
i - number of numbers placed
j - number of connected components
k - The "total cost" (assuming that all empty positions contain a[i+1} and a[n+1]=INF). Use this cost is very important.
l - number of endpoints that are filled
For example, {?, ?, 3, ?, 2, 1} would be counted in dp[3][2][5][1]
*/
int a[107];

int N, L;


int main() {
    debug = false;
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> L;

    if (N == 1) {
        cout << 1 << endl; return 0;
    }

	for (int i = 1; i <= N; i++) cin >> a[i];
	sort(a + 1, a + N + 1);
	a[N + 1] = 10000; // INF

	dp[0][0][0][0] = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			for (int k = 0; k <= L; k++) {
				for (int m = 0; m <= 2; m++) {

                    /// imagine that all ? are placed with a[i] (so cost of ? is 0) and now changed to a[i+1]
					int cost_diff = (2 * j - m) * (a[i + 1] - a[i]);

					if (i + j + 1 - m > N) continue;    // number of points > N
					if (k - cost_diff < 0) continue;    // no initial stage to reach this

					/// Case 1: We inserted a[i] to form a new component that doesn't contain an endpoint of the permutation.
					dp[i][j][k][m] += dp[i - 1][j - 1][k - cost_diff][m];

					/// Case 2: We inserted a[i] to form a new component that contain an endpoint of the permutation.
					/// if m==1, the original condition is m=0 so we can put on either side
					/// if m==2, the original condition is m=1 which means one end is already occupied and we can only add to one end
					if (m==1) dp[i][j][k][m] += 2 * dp[i - 1][j - 1][k - cost_diff][m - 1];
					if (m==2) dp[i][j][k][m] += 1 * dp[i - 1][j - 1][k - cost_diff][m - 1];

					/// Case 3: We appended a[i] to an existing component such that it doesn't contain an end of the permutation.
					/// There were 2j - m component endpoints to choose from : Note that we don't care about the relative orders
					/// of the connected components for each DP state since we are considering all permutations
					/// (Imagine that they're just free-floating components that we can pluck out of space and join.)
					dp[i][j][k][m] += (2 * j - m) * dp[i - 1][j][k - cost_diff][m];

					/// Case 4: We appended a[i] to an existing component such that it contains an end of the permutation.
					/// This is only possible if m > 0.
					/// If m==1, the original stage is m=0, then there were 2j component endpoints to choose from (can append to both sides)
					if (m == 1) dp[i][j][k][m] += 2 * j * dp[i - 1][j][k - cost_diff][m - 1];
					/// if m==2, the original state is m=1 meaning 1 end is already occupied so there are j-1 component ends
					/// since we can only append to one side
					/// (special case is i=N which means j=1)
					if (m == 2) {
						if (i == N) dp[i][j][k][m] += dp[i - 1][j][k - cost_diff][m - 1];
						else if (j > 1) dp[i][j][k][m] += (j - 1) * dp[i - 1][j][k - cost_diff][m - 1];
					}

					/// Case 5:  We inserted a[i] to join two existing components. Original state has (j+1) components
					/// if m=0, there are j(j+1) ordered pair
					if (m==0) {
                        dp[i][j][k][m] += j * (j + 1) * dp[i - 1][j + 1][k - cost_diff][m];
					} else if(m==1) {
					    /// if m==1, one component is already at the end and you can not move it, there are j*j ordered pair
                        dp[i][j][k][m] += j * j * dp[i - 1][j + 1][k - cost_diff][m];
					} else {
                        /// If m==2, there were j(j - 1) ordered pairs of components to choose from
                        /// unless i=N, where you just join 2 component to form a complete line
						if (i == N) dp[i][j][k][m] += dp[i - 1][j + 1][k - cost_diff][m];
						else dp[i][j][k][m] += j * (j - 1) * dp[i - 1][j + 1][k - cost_diff][m];
					}

					dp[i][j][k][m] %= MOD;
				}
			}
		}
	}

	ll ans = 0;
	for (int i = 0; i <= L; i++) ans += dp[N][1][i][2];
	cout << ans % MOD << endl;

    if(debug) cout << endl << "EOL" << endl;

}

/*
4 10
3 6 2 9

8 35
3 7 1 5 10 2 11 6

*/

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 460 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 588 KB Output is correct
14 Correct 1 ms 588 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 1 ms 588 KB Output is correct
21 Correct 2 ms 2380 KB Output is correct
22 Correct 64 ms 35724 KB Output is correct
23 Correct 94 ms 47384 KB Output is correct
24 Correct 85 ms 46788 KB Output is correct
25 Correct 96 ms 50500 KB Output is correct
26 Correct 84 ms 45964 KB Output is correct
27 Correct 34 ms 23492 KB Output is correct
28 Correct 42 ms 26832 KB Output is correct
29 Correct 69 ms 41148 KB Output is correct
30 Correct 98 ms 50788 KB Output is correct