Submission #132212

#	Time	Username	Problem	Language	Result	Execution time	Memory
132212		godwind	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	255 ms	31440 KiB

skyscraper

#pragma GCC optimize("Ofast")
/*#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
                        
using namespace std;
                        
template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}
                        
template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}
  
#define int long long
#define ghost signed
#define left left228
#define right right228
#define prev prev228
#define list list228

const int MOD = 1e9 + 7;

int mod(int x) {
	x %= MOD;
	if (x < 0) x += MOD;
	return x;
}

void add(int &x, int y) {
	x += y;
	if (x >= MOD) x -= MOD;
}

int a[105];
int dp[105][105][2005][2][2];

ghost main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	sort(a + 1, a + n + 1);
	if (n == 1) {
		cout << 1 << '\n';
		return 0;
	}
    if (n == 2) {
        if (a[2] - a[1] <= m) {
            cout << 2 << '\n';
        } else {
            cout << 0 << '\n';
        }
        return 0;
    }
	dp[1][1][2 * (a[2] - a[1])][0][0] = 1;
	dp[1][0][a[2] - a[1]][1][0] = 1;
	dp[1][0][a[2] - a[1]][0][1] = 1;
	a[n + 1] = a[n];
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j <= i; ++j) {
			for (int sum = 0; sum <= m; ++sum) {
				for (int first = 0; first < 2; ++first) {
					for (int last = 0; last < 2; ++last) {
						if (!dp[i][j][sum][first][last]) continue;
                        int d = a[i + 2] - a[i + 1];
                        int DP = dp[i][j][sum][first][last];
						add(dp[i + 1][j + 1][sum + (2 * (j + 1) + first + last) * d][first][last], DP); // create new component
                        add(dp[i + 1][j][sum + (2 * j + first + last) * d][first][last], mod((2 * j + first + last) * DP)); // add to component
                        if (!first) {
                            add(dp[i + 1][j][sum + (2 * j + 1 + last) * d][1][last], DP); // make first component
                            if (j) {
                                // cout << "dp[" << i + 1 << "][" << j - 1 << "][" << sum + (2 * (j - 1) + 1 + last) 
                                add(dp[i + 1][j - 1][sum + (2 * (j-1) + 1 + last) * d][1][last], mod(j * DP)); // make first component and merge with previous
                            }
                        } else if (j) {
                            add(dp[i + 1][j - 1][sum + (2 * (j - 1) + first + last) * d][first][last], mod(j * DP)); // merge some component with first
                        }
                        if (!last) {
                            add(dp[i + 1][j][sum + (2 * j + first + 1) * d][first][1], DP); // make last component
                            if (j) {
                                add(dp[i + 1][j - 1][sum + (2 * (j - 1) + first + 1) * d][first][1], mod(j * DP)); // make last component and merge with previous
                            }
                        } else if (j) {
                            add(dp[i + 1][j - 1][sum + (2 * (j - 1) + first + last) * d][first][last], mod(j * DP)); // merge some component with last
                        }
                        if (j > 1) {
                            add(dp[i + 1][j - 1][sum + (2 * (j-1) + first + last) * d][first][last], mod((j-1) * mod(j * DP))); // merge 2 components using us
                        }
					}
				}
			}
		}
	}
    int res = 0;
	for (int w = 0; w <= m; ++w) {
		add(res, dp[n - 1][0][w][1][1]);
		add(res, dp[n - 1][0][w][1][0]);
		add(res, dp[n - 1][0][w][0][1]);
	}
	cout << res << '\n';
    return 0;
} // kek ;

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