Submission #631103

#	Time	Username	Problem	Language	Result	Execution time	Memory
631103		urosk	Skyscraper (JOI16_skyscraper)	C++14	20 / 100	2094 ms	269980 KiB

skyscraper

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;
#define mod 1000000007
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}

typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
#define maxn 105
ll n,L;
ll a[maxn];
map<ll,ll> dp[maxn][maxn][2][2];

int main(){
	daj_mi_malo_vremena
    cin >> n >> L;
    for(ll i = 1;i<=n;i++) cin >> a[i];
    if(n==1){cout<<1<<endl;return 0;}
    sort(a+1,a+n+1);
    dp[1][1][1][0][-a[1]] = 1;
    dp[1][1][0][1][-a[1]] = 1;
    dp[1][1][0][0][-2*a[1]] = 1;
	for(ll i = 2;i<=n;i++){
        for(ll j = 1;j<=n;j++){
            for(ll l = 0;l<=1;l++){
                for(ll r = 0;r<=1;r++){
                    for(pll p : dp[i-1][j][l][r]){
                        ll k = p.fi;
                        ll cnt = p.sc;
                        if(k>L) break;
                        dp[i][j][l][r][k] = add(dp[i][j][l][r][k],mul(cnt,2*j-l-r));
                        if(!l) dp[i][j][1][r][k+a[i]] = add(dp[i][j][1][r][k+a[i]],cnt);
                        if(!r) dp[i][j][l][1][k+a[i]] = add(dp[i][j][l][1][k+a[i]],cnt);
                        dp[i][j+1][l][r][k-2*a[i]] = add(dp[i][j+1][l][r][k-2*a[i]],mul(cnt,j+1-l-r));
                        if(!l) dp[i][j+1][1][r][k-a[i]] = add(dp[i][j+1][1][r][k-a[i]],cnt);
                        if(!r) dp[i][j+1][l][1][k-a[i]] = add(dp[i][j+1][l][1][k-a[i]],cnt);
                        dp[i][j-1][l][r][k+2*a[i]] = add(dp[i][j-1][l][r][k+2*a[i]],mul(cnt,j-1));
                    }
                }
            }
        }
	}
	ll ans = 0;
	for(pll p : dp[n][1][1][1]){
        ll k = p.fi;
        ll cnt = p.sc;
        if(k<=L) ans = add(ans,cnt);
	}
	cout<<ans<<endl;
	return 0;
}

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