Submission #1297231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297231		danglayloi1	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	130 ms	130544 KiB

skyscraper

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=105;
int add(int a, int b)
{
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
int mul(int a, int b)
{
    ll tmp=1ll*a*b;
    if(tmp>=mod) tmp%=mod;
    return tmp;
}
int n, l, a[nx], dp[nx][nx][1005][3];
int f(int i, int cc, int cur, int ends)
{
    if(cur>l || ends>2) return 0;
    if(i>1 && cc<=0) return 0;
    if(i==n+1) return (cc==1 && ends==2);
    int &res=dp[i][cc][cur][ends];
    if(res!=-1) return res;
    res=0;
    int nxt=cur+(2*cc-ends)*(a[i]-a[i-1]);
    // ends
    // new cc
    res=add(res, mul(cc+1-ends, f(i+1, cc+1, nxt, ends)));
    // merge 2 cc
    res=add(res, mul(cc-1, f(i+1, cc-1, nxt, ends)));
    // extend a cc
    res=add(res, mul(2*cc-ends, f(i+1, cc, nxt, ends)));
    // ends+1
    // new cc
    res=add(res, mul(2-ends, f(i+1, cc+1, nxt, ends+1)));
    // extend a cc
    res=add(res, mul(2-ends, f(i+1, cc, nxt, ends+1)));
    return res;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>l;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    if(n==1) return cout<<1, 0;
    sort(a+1, a+n+1);
    memset(dp, -1, sizeof(dp));
    cout<<f(1, 0, 0, 0);
}

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