Submission #438722

#	Time	Username	Problem	Language	Result	Execution time	Memory
438722		alirezasamimi100	Skyscraper (JOI16_skyscraper)	C++17	15 / 100	2 ms	716 KiB

skyscraper

#include <bits/stdc++.h>
/*#pragma GCC optimize("Ofast,unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")*/
//#pragma GCC optimize("O2")
/*#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
using namespace std;
using ll = long long int;
using ld = long double;
#define F first
#define S second
#define pb push_back
//#define mp make_pair
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=1e2+10,LN=20,M=3.5e7+10,SQ=350,BS=737,inf=1e9+10;
const ll INF=1e15;
const ld ep=1e-7;
const int MH=1000696969,MOD=1000000007,MD=998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
ll n,k,a[N],dp[N][N][1005][3],ans;
int main(){
    fast_io;
    cin >> n >> k;
    for(ll i=1; i<=n; i++){
        cin >> a[i];
    }
    dp[0][0][0][0]=1;
    sort(a+1,a+n+1);
    for(ll i=1; i<=n; i++){
        for(ll j=1; j<=i; j++){
            for(ll x=0; x<=k; x++){
                for(ll y=0; y<3; y++){
                    ll c=(2*j-y)*(a[i+1]-a[i]);
                    if(c>x || i+j-y>=n) continue;
                    dp[i][j][x][y]+=dp[i-1][j-1][x-c][y]+(2*j-y)*dp[i-1][j][x-c][y];
                    if(y) dp[i][j][x][y]+=(3^y)*dp[i-1][j-1][x-c][y-1];
                    if(y==1){
                        dp[i][j][x][y]+=2*j*dp[i-1][j][x-c][y-1]+j*j*dp[i-1][j+1][x-c][y];
                    }else if(y==2){
                        if(i==n) dp[i][j][x][y]+=dp[i-1][j+1][x-c][y]+dp[i-1][j][x-c][y-1];
                        else dp[i][j][x][y]+=(j-1)*dp[i-1][j][x-c][y-1]+j*(j-1)*dp[i-1][j+1][x-c][y];
                    }else{
                        dp[i][j][x][y]+=j*(j+1)*dp[i-1][j+1][x-c][y];
                    }
                    dp[i][j][x][y]%=MOD;
                }
            }
        }
    }
    for(ll i=0; i<=k; i++) ans+=dp[n][1][i][2];
    cout << ans%MOD << '\n';
    return 0;
}

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