Submission #442309

#	Time	Username	Problem	Language	Result	Execution time	Memory
442309		Pajaraja	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	400 ms	2760 KiB

skyscraper

#include <bits/stdc++.h>
#define MAXN 107
#define MAXL 2007
#define LAYERS 25
#define MOD 1000000007
using namespace std;
long long dp[2][LAYERS][MAXL][3],a[MAXN];
int main()
{
    int n; long long lim; cin>>n>>lim;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n); a[n]=a[n-1];
    dp[n&1][0][0][0]=1;
    for(int i=n-1;i>=0;i--)
    {
        int l=i&1;
        for(int j=0;j<LAYERS;j++) for(int k=0;k<MAXL;k++) for(int g=0;g<3;g++)
        {
            dp[l][j][k][g]=0;
            if(i<n-1 && k-(2*j-g)*(a[i+1]-a[i])>=0) dp[l][j][k][g]=(dp[l][j][k][g]+dp[l^1][j][k-(2*j-g)*(a[i+1]-a[i])][g]*(2*j-g))%MOD;
            if(j>0 && k-(2*j-2-g)*(a[i+1]-a[i])>=0) dp[l][j][k][g]=(dp[l][j][k][g]+dp[l^1][j-1][k-(2*j-2-g)*(a[i+1]-a[i])][g])%MOD;
            if((j>1 || g<2) && j+1<LAYERS && k-(2*j+2-g)*(a[i+1]-a[i])>=0) dp[l][j][k][g]=(dp[l][j][k][g]+dp[l^1][j+1][k-(2*j+2-g)*(a[i+1]-a[i])][g]*(j+1-(g+1)/2)*(j-g/2))%MOD;
            if(g>0 && j>0 && k-(2*j-1-g)*(a[i+1]-a[i])>=0) dp[l][j][k][g]=(dp[l][j][k][g]+dp[l^1][j-1][k-(2*j-1-g)*(a[i+1]-a[i])][g-1])%MOD;
            if((j>1 || g<2) && g>0 && k-(2*j+1-g)*(a[i+1]-a[i])>=0) dp[l][j][k][g]=(dp[l][j][k][g]+dp[l^1][j][k-(2*j+1-g)*(a[i+1]-a[i])][g-1]*(j+1-g))%MOD;
        }
    }
    for(int k=0;k<MAXL;k++) if(k-2*(a[1]-a[0])>=0) dp[0][1][k][2]=(dp[0][1][k][2]+dp[1][2][k-2*(a[1]-a[0])][2])%MOD;
    for(int k=0;k<MAXL;k++) if(k-1*(a[1]-a[0])>=0) dp[0][1][k][2]=(dp[0][1][k][2]+dp[1][1][k-1*(a[1]-a[0])][1])%MOD;
    long long sol=0;
    for(int k=0;k<=lim;k++) sol=(sol+2*dp[0][1][k][2])%MOD;
    if(n==1) sol=1;
    cout<<sol;
}

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