Submission #1155798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155798		raczek	Skyscraper (JOI16_skyscraper)	C++20	15 / 100	1 ms	1036 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto operator <<(auto& o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X...) cerr<<"["#X"]: ", [](auto...$) {((cerr<<$<<"; "),...)<<endl;}(X)
#else 
#define debug(...){}
#endif
#define int long long
const int INF = 1e18+7;
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define eb emplace_back
int32_t main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n, l;
	cin>>n>>l;
	vector<int> a(n);
	for(auto& v : a) cin>>v;
	sort(a.begin(), a.end());
	const int MOD = 1e9+7;
	vector dp(n+1, vector(l+1, vector(3, 0LL)));
	dp[0][0][0] = 1;
	auto print = [&]()
	{
		for(auto v : dp)
			debug(v);
	};
	for(auto& v : a)
	{
		print();
		int idx = &v-&(*a.begin());
		debug(idx);
		int nxt = idx == n-1 ? (1005) : a[idx+1];
		auto ndp = dp;
		for(auto& x : dp)
			for(auto& u : x)
				for(auto& y : u)
					y = 0;
		for(int i=1;i<=idx+1;i++)
		{
			for(int k = 0; k <= l; k++)
			{
				for(int m = 0;m <= 2; m++)
				{
					dp[i][k][m] = 0;
					int C = k - (2*i-m)*(nxt - v);
					
					if(idx + i + 2 - m > n || C < 0) continue;
					//nowa sklejka (nie na koncu perm):
					dp[i][k][m] += ndp[i-1][C][m];

					//nowa sklejka (na koncu perm):
					if(m > 0) dp[i][k][m] += (2-(m-1))*ndp[i-1][C][m-1];
					
					//rozszerzenie którejś sklejki, ale tak, żeby nie zakryć żadnego końca:
					dp[i][k][m] += (2*i - m)*ndp[i][C][m];

					//rozszerzenie którejś sklejki tak, żeby zakryć któryś koniec:
					if(m == 1) dp[i][k][m] += 2*i*ndp[i][C][m-1];
					if(m == 2) dp[i][k][m] += (i-1 != 0 ? i-1 : (idx == n-1 ? 1 : 0))*ndp[i][C][m-1];

					//sklejenie sklejek (było (i+1) sklejek)
					if(m == 0) dp[i][k][m] += (i+1)*(i+1-1)*ndp[i+1][C][m];
					if(m == 1) dp[i][k][m] += (i+1-1)*ndp[i+1][C][m] + (i+1-2 > 0 ? (i+1-1)*(i+1-2)*ndp[i+1][C][m] : 0);
					//dwie sklejki przyklejone do końców i pomiędzy nimi coś jeszcze:
					if(m == 2 && i+1 >= 3) dp[i][k][m] += 2*(i+1-2)*ndp[i+1][C][m] + (i+1-2)*(i+1-3)*ndp[i+1][C][m];
					//tylko dwie sklejki przyklejone do końcow (jeżeli chce je skleić to musze dodawać ostatni element):
					if(m == 2 && idx == n-1) dp[i][k][m] += ndp[i+1][C][m];


					dp[i][k][m] %= MOD;
				}
			}
		}
	}
	print();
	int res = 0;
	for(int k=0;k<=l;k++)
		res = (res + dp[1][k][2])%MOD;
	cout<<res;
}

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