Submission #1191262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191262		alexdd	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	144 ms	199740 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;


int n,lim;
int a[105];
int dp[105][105][1005][5];
signed main()
{
    cin>>n>>lim;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    if(n==1)
    {
        cout<<1;
        return 0;
    }
    sort(a+1,a+1+n);
    dp[0][0][0][0] = 1;
    int rez=0;
    for(int i=1;i<=n;i++)
    {
        for(int cnt=0;cnt<=i-1;cnt++)
        {
            for(int sum=0;sum<=lim;sum++)
            {
                for(int margini=0;margini<=2;margini++)
                {
                    dp[i-1][cnt][sum][margini] %= MOD;
                    int x = dp[i-1][cnt][sum][margini];

                    if(x==0)
                        continue;

                    int newsum = sum + (a[i]-a[i-1])*(2*cnt - margini);

                    if(newsum > lim)
                        continue;

                    dp[i][cnt + 1][newsum][margini] += x;///incepe o secv noua
                    dp[i][cnt + 1][newsum][margini + 1] += x*(2-margini)%MOD;///incepe o secv noua la margine
                    dp[i][cnt][newsum][margini] += x * (2*cnt - margini)%MOD;///se continua o secv
                    if(cnt-1 >= 1) dp[i][cnt - 1][newsum][margini] += x * ((cnt-margini)*(cnt-margini-1)%MOD + margini * (cnt-margini))%MOD;///se unesc 2 secv
                    dp[i][cnt][newsum][margini + 1] += x * (2-margini)%MOD * (cnt - margini)%MOD;

                    if(i==n)
                    {
                        if(cnt==1 && margini==1)
                        {
                            rez += x;
                        }
                        if(cnt==2 && margini==2)
                        {
                            rez += x;
                        }
                        rez%=MOD;
                    }
                }
            }
        }
    }
    cout<<rez%MOD;
    return 0;
}
/*

4 10
3 6 2 9

8 35
3 7 1 5 10 2 11 6

*/

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