Submission #488464

#	Time	Username	Problem	Language	Result	Execution time	Memory
488464		Tenis0206	Skyscraper (JOI16_skyscraper)	C++11	100 / 100	406 ms	101444 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const int Mod = 1e9 + 7;

int n,l;
int v[1005];

int dp[105][105][2005][2][2];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
  //  freopen("nr.in","r",stdin);
  //  freopen("nr.out","w",stdout);
    cin>>n>>l;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    sort(v+1,v+n+1);
    v[n+1] = v[n];
    dp[1][0][0][0][0] = 1;
    dp[1][0][v[2]-v[1]][0][1] = 1;
    dp[1][0][v[2]-v[1]][1][0] = 1;
    dp[1][0][2*(v[2]-v[1])][1][1] = 1;
    for(int i=1; i<n; i++)
    {
        for(int j=0; j<i; j++)
        {
            for(int s=0; s<=l; s++)
            {
                ///adaugam un element in centru
                for(int a=0; a<=1; a++)
                {
                    for(int b=0; b<=1; b++)
                    {
                        ///taiem ambele spatii
                        if(j>0)
                        {
                            dp[i+1][j-1][s+(2*(j-1)+a+b)*(v[i+2]-v[i+1])][a][b]+=(1LL * dp[i][j][s][a][b] * j) % Mod;
                            dp[i+1][j-1][s+(2*(j-1)+a+b)*(v[i+2]-v[i+1])][a][b]%=Mod;
                        }
                        ///taiem un singur spatiu
                        dp[i+1][j][s+(2*j+a+b)*(v[i+2]-v[i+1])][a][b]+=(1LL * dp[i][j][s][a][b] * j * 2) % Mod;
                        dp[i+1][j][s+(2*j+a+b)*(v[i+2]-v[i+1])][a][b]%=Mod;
                        ///taiem ambele spatii
                        dp[i+1][j+1][s+(2*(j+1)+a+b)*(v[i+2]-v[i+1])][a][b]+=(1LL * dp[i][j][s][a][b] * j) % Mod;
                        dp[i+1][j+1][s+(2*(j+1)+a+b)*(v[i+2]-v[i+1])][a][b]%=Mod;
                    }
                }
                ///adaugam un element in fata
                for(int b=0;b<=1;b++)
                {
                    ///se creaza un nou spatiu

                    ///ramane loc de adaugat in fata
                    dp[i+1][j+1][s+(2*(j+1)+1+b)*(v[i+2]-v[i+1])][1][b]+=dp[i][j][s][1][b];
                    dp[i+1][j+1][s+(2*(j+1)+1+b)*(v[i+2]-v[i+1])][1][b]%=Mod;
                    ///nu ramane loc de adaugat in fata
                    dp[i+1][j+1][s+(2*(j+1)+0+b)*(v[i+2]-v[i+1])][0][b]+=dp[i][j][s][1][b];
                    dp[i+1][j+1][s+(2*(j+1)+0+b)*(v[i+2]-v[i+1])][0][b]%=Mod;

                    ///nu se creeaza un nou spatiu

                    ///ramane loc de adaugat in fata
                    dp[i+1][j][s+(2*j+1+b)*(v[i+2]-v[i+1])][1][b]+=dp[i][j][s][1][b];
                    dp[i+1][j][s+(2*j+1+b)*(v[i+2]-v[i+1])][1][b]%=Mod;
                    ///nu ramane loc de adaugat in fata
                    dp[i+1][j][s+(2*j+0+b)*(v[i+2]-v[i+1])][0][b]+=dp[i][j][s][1][b];
                    dp[i+1][j][s+(2*j+0+b)*(v[i+2]-v[i+1])][0][b]%=Mod;

                }

                ///adaugam un element in spate
                for(int a=0;a<=1;a++)
                {
                    ///se creeaza un nou spatiu

                    ///ramane loc de adaugat in spate
                    dp[i+1][j+1][s+(2*(j+1)+a+1)*(v[i+2]-v[i+1])][a][1]+=dp[i][j][s][a][1];
                    dp[i+1][j+1][s+(2*(j+1)+a+1)*(v[i+2]-v[i+1])][a][1]%=Mod;
                    ///nu ramane loc de adaugat in fata
                    dp[i+1][j+1][s+(2*(j+1)+a+0)*(v[i+2]-v[i+1])][a][0]+=dp[i][j][s][a][1];
                    dp[i+1][j+1][s+(2*(j+1)+a+0)*(v[i+2]-v[i+1])][a][0]%=Mod;

                    ///nu se creeaza un nou spatiu
                    dp[i+1][j][s+(2*j+a+1)*(v[i+2]-v[i+1])][a][1]+=dp[i][j][s][a][1];
                    dp[i+1][j][s+(2*j+a+1)*(v[i+2]-v[i+1])][a][1]%=Mod;
                    ///nu ramane loc de adaugat in fata
                    dp[i+1][j][s+(2*j+a+0)*(v[i+2]-v[i+1])][a][0]+=dp[i][j][s][a][1];
                    dp[i+1][j][s+(2*j+a+0)*(v[i+2]-v[i+1])][a][0]%=Mod;
                }
            }
        }
    }
    long long rez = 0;
    for(int i=0;i<=l;i++)
    {
        rez+=dp[n][0][i][0][0];
        rez%=Mod;
    }
    cout<<rez<<'\n';
    return 0;
}

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