Submission #245917

#	Time	Username	Problem	Language	Result	Execution time	Memory
245917		Goolakh	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	218 ms	287368 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Os")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e2+10, maxm=1e3+10, lg=21, mod=1e9+7, inf=1e18;

ll n,L,a[maxn],dp[maxn][maxn][maxm][3];
ll moz(ll i,ll cc,ll sum,ll tend){
	if(sum>L || (cc==0 && i!=1)) return 0;
	if(i==n+1) return tend==2 && cc==1;
	ll &x=dp[i][cc][sum][tend];
	if(x!=-1) return x;
	x=0;
	sum+=(a[i]-a[i-1])*(2*cc-tend);
	if(cc>=1) x+=(2*cc-tend)*moz(i+1,cc,sum,tend); // merge1
	if(cc>=2) x+=(cc-1)*moz(i+1,cc-1,sum,tend); // merge2
	x+=(cc+1-tend)*moz(i+1,cc+1,sum,tend); // mostaghel vasat
	if(tend<2){
		x+=(2-tend)*moz(i+1,cc+1,sum,tend+1); // mostaghel end
		x+=(2-tend)*moz(i+1,cc,sum,tend+1); // bechasbe be tah bokone end
	}
	return x%=mod;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n>>L;
	if(n==1) return cout<<1,0;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	memset(dp,-1,sizeof(dp));
	cout<<moz(1,0,0,0);
 	
	return 0;
}

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