Submission #1224881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224881		MarwenElarbi	Skyscraper (JOI16_skyscraper)	C++20	20 / 100	67 ms	60484 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
int n,l;
long long dp[105][51][1005][3];
vector<int> tab(105);
int main(void)
{
    cin>>n>>l;
    if(n==1) {
      cout <<1<<endl;
      return 0;
    }
    tab.resize(n);
    for (int i = 0; i < n; ++i)
    {
        cin>>tab[i];
    }
    sort(tab.begin(),tab.end());
    dp[0][0][0][0]=1;
    for (int i = 1; i <= n; ++i)
    {
        for (int c = 1; c <= i; ++c)
        {
            for (int b = 0; b < 3; ++b)
            {
                for (int sum = 0; sum <= l; ++sum)
                {
                    int oldsum=sum;
                    if(i<n) oldsum-=(c*2-b)*(tab[i]-tab[i-1]);
                    if(oldsum<0) continue;
                    if(c+1<=i-1) dp[i][c][sum][b]+=dp[i-1][c+1][oldsum][b]*c;
                    dp[i][c][sum][b]+=dp[i-1][c-1][oldsum][b]*(c-b);
                    dp[i][c][sum][b]+=dp[i-1][c][oldsum][b]*(2*c-b);
                    if(b>0) dp[i][c][sum][b]+=dp[i-1][c-1][oldsum][b-1]*(3-b);
                    if(b>0) dp[i][c][sum][b]+=dp[i-1][c][oldsum][b-1]*(3-b);
                    dp[i][c][sum][b]%=MOD;
                    //cout <<i<<" "<<c<<" "<<sum<<" "<<b<<" "<<dp[i][c][sum][b]<<endl;
                }
            }
        }
    }
    long long ans=0;
    for (int i = 0; i <= l; ++i)
    {
        ans+=dp[n][1][i][2];
        ans%=MOD;
    }
    cout <<ans<<endl;
}

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