Submission #602271

#	Time	Username	Problem	Language	Result	Execution time	Memory
602271		Evirir	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	343 ms	130400 KiB

skyscraper

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
const ll INF = ll(1e18);
const int MOD = 1e9+7;

const bool DEBUG = 0;
const int MAXN = 105;
const int MAXA = 1005;
const int LG = 21;

ll add(ll a, ll b, ll m = MOD)
{
	a+=b;
	if(abs(a)>=m) a%=m;
	if(a<0) a+=m;
	return a;
}
ll mult(ll a, ll b, ll m = MOD)
{
	if(abs(a)>=m) a%=m;
	if(abs(b)>=m) b%=m;
	a*=b;
	if(abs(a)>=m) a%=m;
	if(a<0) a+=m;
	return a;
}
inline void radd(ll &a, ll b)
{
	a = add(a, b);
}

ll n,L;
ll a[MAXN];
ll dp[MAXN][MAXN][MAXA][3];  // current num%2, # of cc, sum, front done + back done

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>L;
	fore(i,1,n) cin>>a[i];
	sort(a+1,a+n+1);

	// special case: can use up front and back at the same time
	if(n==1)
	{
		cout<<1<<'\n';
		return 0;
	}

	dp[0][0][0][0] = 1;
	fore(i,1,n)
	{
		fore(j,1,n) fore(k,0,L)
		{
			ll val = a[i] - a[i-1];
			ll inc;

			// --- put front/back ---
			fore(l,1,2)
			{
				// new cc
				inc=((j-1)*2-(l-1))*val;
				if(k-inc>=0) radd(dp[i][j][k][l], mult(2-(l-1), dp[i-1][j-1][k-inc][l-1]));

				// extend cc
				inc=(j*2-(l-1))*val;
				if(k-inc>=0) radd(dp[i][j][k][l], mult(2-(l-1), dp[i-1][j][k-inc][l-1]));
			}

			// --- put middle ---
			fore(l,0,2)
			{
				// new cc
				inc=((j-1)*2-l)*val;
				if(k-inc>=0) radd(dp[i][j][k][l], mult((j-1)+1-l, dp[i-1][j-1][k-inc][l]));

				// extend cc
				inc=(j*2-l)*val;
				if(k-inc>=0) radd(dp[i][j][k][l], mult(j*2-l, dp[i-1][j][k-inc][l]));

				// merge cc
				inc=((j+1)*2-l)*val;
				if(k-inc>=0) radd(dp[i][j][k][l], mult((j+1)-1, dp[i-1][j+1][k-inc][l]));
			}
		}
	}

	ll ans=0;
	fore(k,0,L) radd(ans, dp[n][1][k][2]);
	cout<<ans<<'\n';
	
	return 0;
}

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