Submission #685058

#	Time	Username	Problem	Language	Result	Execution time	Memory
685058		NeroZein	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	250 ms	2732 KiB

skyscraper

/*
 *    author: NeroZein
 *    created: 23.01.2023 11:07:10
*/
#include <bits/stdc++.h>
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int md = 1e9+7; 

inline void add(int& a, int b) {
	a += b;
	if(a >= md){
		a -= md;
	}
}

inline int mul(int a, int b) {
	return (int)((long long) a * b % md);
}

signed main(){

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	if(n == 1){
		cout << 1 << '\n';
		return 0; 
	}
	sort(a.begin(), a.end());
	vector<vector<array<int, 3>>>dp(n, vector<array<int, 3>>(m + 1));
	//ncc, sum, used endpoints
	dp[1][0][0] = 1; 
	dp[1][0][1] = 2;
	for (int i = 1; i < n; ++i) {
		vector<vector<array<int, 3>>>pd(n, vector<array<int, 3>>(m + 1));
		for (int j = 1; j < n; ++j) {
			for(int k = 0; k <= m; ++k) {
				for(int e = 0; e < 3; ++e){
					int diff = (2 * j - e) * (a[i] - a[i-1]); 
					if(k + diff > m){
						continue; 
					}
					//merge two cc
					if(j > 1) {
						add(pd[j - 1][k + diff][e], mul(j - 1, dp[j][k][e]));
					}
					//create a cc 
					if(j + 1 < n) {
						add(pd[j + 1][k + diff][e], mul(j + 1 - e, dp[j][k][e]));
					}
					//create a cc on the endpoints
					if(j + 1 < n && e < 2){
						add(pd[j + 1][k + diff][e + 1], mul(2 - e, dp[j][k][e]));
					}
					//add to the left or right to an already existing component but not become an endpoint
					add(pd[j][k + diff][e], mul(2 * j - e, dp[j][k][e]));
					//add to the left or right to an already existing component but become an endpoint
					if(e < 2){
						add(pd[j][k + diff][e + 1], mul(2 - e, dp[j][k][e]));
					}
				}
			}
		}
		swap(dp, pd);
	}
	int ans = 0;
	for(int i = 0; i <= m; ++i){
		add(ans, dp[1][i][2]);
	}
	cout << ans << '\n';

}

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