Submission #452152

#	Time	Username	Problem	Language	Result	Execution time	Memory
452152		gmyu	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	98 ms	50788 KiB

skyscraper

/*
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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80