Submission #488637

#	Time	Username	Problem	Language	Result	Execution time	Memory
488637		Savu_Stefan_Catalin	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	1428 ms	378952 KiB

skyscraper

#include <iostream>
#include <algorithm>
using namespace std;
long long n,s,i,j,S,F,L,a[1005],dp[105][105][2005][2][2],sum,M;
int main()
{
    M=1000000007;
    cin>>n>>L;
    for (i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    dp[1][0][0][0][0]=1;
    dp[1][0][0][0][1]=1;
    dp[1][0][0][1][0]=1;
    dp[1][0][0][1][1]=1;
    for (i=1;i<n;++i)
    for (j=0;j<=n;++j)
    for (s=0;s<=L;++s)
    for (S=0;S<=1;++S)
    for (F=0;F<=1;++F)
    {
    if (j>0)
    dp[i+1][j-1][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][F]+=dp[i][j][s][S][F]*j;
    dp[i+1][j+0][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][F]+=dp[i][j][s][S][F]*j*2;
    dp[i+1][j+1][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][F]+=dp[i][j][s][S][F]*j;

    if (S==1) dp[i+1][j+1][s+(2*j+S+F)*(a[i+1]-a[i+0])][0][F]+=dp[i][j][s][S][F];
    if (S==1) dp[i+1][j+1][s+(2*j+S+F)*(a[i+1]-a[i+0])][1][F]+=dp[i][j][s][S][F];
    if (S==1) dp[i+1][j][s+(2*j+S+F)*(a[i+1]-a[i+0])][0][F]+=dp[i][j][s][S][F];
    if (S==1) dp[i+1][j][s+(2*j+S+F)*(a[i+1]-a[i+0])][1][F]+=dp[i][j][s][S][F];

    if (F==1) dp[i+1][j+1][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][0]+=dp[i][j][s][S][F];
    if (F==1) dp[i+1][j+1][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][1]+=dp[i][j][s][S][F];
    if (F==1) dp[i+1][j][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][0]+=dp[i][j][s][S][F];
    if (F==1) dp[i+1][j][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][1]+=dp[i][j][s][S][F];


    dp[i+1][j-1][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][F]%=M;
    dp[i+1][j+0][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][F]%=M;
    dp[i+1][j+1][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][F]%=M;

    if (S==1) dp[i+1][j+1][s+(2*j+S+F)*(a[i+1]-a[i+0])][0][F]%=M;
    if (S==1) dp[i+1][j+1][s+(2*j+S+F)*(a[i+1]-a[i+0])][1][F]%=M;
    if (S==1) dp[i+1][j][s+(2*j+S+F)*(a[i+1]-a[i+0])][0][F]%=M;
    if (S==1) dp[i+1][j][s+(2*j+S+F)*(a[i+1]-a[i+0])][1][F]%=M;

    if (F==1) dp[i+1][j+1][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][0]%=M;
    if (F==1) dp[i+1][j+1][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][1]%=M;
    if (F==1) dp[i+1][j][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][0]%=M;
    if (F==1) dp[i+1][j][s+(2*j+S+F)*(a[i+1]-a[i+0])][S][1]%=M;

    }
    for (s=0;s<=L;++s)
        sum=(sum+dp[n][0][s][0][0])%M;
    cout<<sum;
    return 0;
}

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