제출 #1207171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207171		HoriaHaivas	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	172 ms	105320 KiB

skyscraper

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

const int mod=1e9+7;
int dp[105][105][2005][4];
int v[105];

int mul(int a, int b)
{
    if (b<0)
        return 0;
    int c;
    c=a*b;
    c%=mod;
    return c;
}

void add(int &a, int b)
{
    a+=b;
    a%=mod;
}

signed main()
{
    //ifstream fin("felinare.in");
    //ofstream fout("felinare.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,i,j,k,L,diff,ans,delta,sum;
    cin >> n >> L;
    for (i=1; i<=n; i++)
    {
        cin >> v[i];
    }
    sort(v+1,v+1+n);
    dp[1][1][0][0]=1;
    dp[1][1][0][1]=2;
    dp[1][1][0][2]=1;
    for (i=2; i<=n; i++)
    {
        for (j=1; j<=i; j++)
        {
            for (k=0; k<=2; k++)
            {
                delta=v[i]-v[i-1];
                diff=(2*j-k)*delta;
                for (sum=0; sum<=L; sum++)
                {
                    if ((sum-(2*j-k)*delta)>=0)
                    {
                        ///alipim, dar nu inchidem
                        add(dp[i][j][sum][k],mul(dp[i-1][j][sum-(2*j-k)*delta][k],(2*j-k)));
                        ///alipim si inchidem un capat
                        if (k-1>=0)
                            add(dp[i][j][sum][k],mul(dp[i-1][j][sum-(2*j-(k-1))*delta][k-1],(2-(k-1))));
                    }
                    if ((sum-(2*(j-1)-k)*delta)>=0)
                    {
                        ///cream comp, dar nu inchidem
                        add(dp[i][j][sum][k],mul(dp[i-1][j-1][sum-(2*(j-1)-k)*delta][k],((j-1)+1-k)));
                        ///cream comp si inchidem
                        if (k-1>=0)
                            add(dp[i][j][sum][k],mul(dp[i-1][j-1][sum-(2*(j-1)-(k-1))*delta][k-1],(2-(k-1))));
                    }
                    if ((sum-(2*(j+1)-k)*delta)>=0)
                    {
                        ///unim
                        add(dp[i][j][sum][k],mul(dp[i-1][j+1][sum-(2*(j+1)-k)*delta][k],((j+1)-1)));
                    }
                }
            }
        }
    }
    ans=0;
    for (i=0; i<=L; i++)
    {
        add(ans,dp[n][1][i][2]);
    }
    cout << ans;
    return 0;
}

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