Submission #1322769

#TimeUsernameProblemLanguageResultExecution timeMemory
1322769hanoonSkyscraper (JOI16_skyscraper)C++20
100 / 100
181 ms260616 KiB
#include <bits/stdc++.h>

#define ll long long
#define int ll
#define ld long double
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define vi vector<int>
#define vvi vector<vi>
#define vvv vector<vvi>
#define vpi vector<pair<int,int>>
#define sz(v) (int)v.size()
#define pb push_back
#define ii pair<int,int>
#define F first
#define S second
using namespace std;
const int mod = 1e9+7, N = 100+5 ,M=1005;
const ll inf = 1e18;
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {-1, 1, 0, 0, 1, -1, 1, -1};

int n,l,a[N],dp[N][N][M][3];

// ith sorted element , #of components , #of ends in final answer
int calc(int i,int comp,int sum,int ends){
    if(sum>l) return 0;
    if(i>n) return comp==1&&ends==2;

    int&ret=dp[i][comp][sum][ends];
    if(~ret) return ret;
    ret=0;

    int newSum=sum+(2*comp-ends)*(a[i]-a[i-1]);

    //// 1- no more ends
    // new comp
    ret=(ret+ 1ll*(comp+1-ends)*calc(i+1,comp+1,newSum,ends)%mod )%mod;
    // extend comp
    if(comp)
        ret=(ret+ 1ll*(2*comp-ends)*calc(i+1,comp,newSum,ends)%mod )%mod;
    // combine 2 comp
    if(comp>=2)
        ret=(ret+ 1ll*(comp-1)*calc(i+1,comp-1,newSum,ends)%mod )%mod;

    //// 2- add a new end
    if(ends<2){
        // new comp
        ret=(ret+ 1ll*(2-ends)*calc(i+1,comp+1,newSum,ends+1)%mod )%mod;
        // extend comp
        if(comp)
            ret=(ret+ 1ll*(2-ends)*calc(i+1,comp,newSum,ends+1)%mod )%mod;
    }

    return ret;
}

void here_we_go_again() {
    cin>>n>>l;
    for (int i = 1; i <= n ; ++i) cin>>a[i];

    if(n==1) {
        cout<<1;
        return;
    }

    sort(a+1,a+n+1);
    memset(dp,-1,sizeof dp);
    cout<<calc(1,0,0,0);

}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);


    int tc = 1;
//    cin >> tc;
    for(int i=1;i<=tc;++i) {
//        cout<<"Case #"<<i<<": ";
        here_we_go_again();
    }

    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...