Submission #476063

#	Time	Username	Problem	Language	Result	Execution time	Memory
476063		nicolaalexandra	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	402 ms	84144 KiB

skyscraper

#include <bits/stdc++.h>
#define DIM 110
#define DIML 1010
#define MOD 1000000007
using namespace std;

int dp[DIM][DIM][DIML][3],v[DIM];
int n,i,comp,nr,cost,L;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");


    cin>>n>>L;
    for (i=1;i<=n;i++)
        cin>>v[i];

    if (n == 1){
        cout<<1;
        return 0;
    }


    sort (v+1,v+n+1);

    /// dp[i][j][l][0/1/2] - nr de permutari cu i elemente, j comp conexe, cost l
    /// si 0 1 sau 2 capete fixate
    dp[0][0][0][0] = 1;
    for (i=1;i<=n;i++)
        for (comp=1;comp<=n;comp++)
            for (cost=0;cost<=L;cost++)
                for (nr=0;nr<=2;nr++){ /// marginile

                    /// creez componenta noua

                    int val = (2 * (comp-1) - nr) * (v[i] - v[i-1]);
                    if (val <= cost){
                        dp[i][comp][cost][nr] += 1LL * dp[i-1][comp-1][cost-val][nr] * (comp - nr) % MOD;
                        if (dp[i][comp][cost][nr] >= MOD)
                            dp[i][comp][cost][nr] -= MOD;
                    }

                    /// leg de o componenta
                    val = (2 * comp - nr) * (v[i] - v[i-1]);
                    if (val <= cost){
                        dp[i][comp][cost][nr] += 1LL * dp[i-1][comp][cost-val][nr] * (comp * 2 - nr) % MOD;
                        if (dp[i][comp][cost][nr] >= MOD)
                            dp[i][comp][cost][nr] -= MOD;
                    }


                    /// unesc doua componente

                    val = (2 * (comp + 1) - nr) * (v[i] - v[i-1]);
                    if (val <= cost){
                        dp[i][comp][cost][nr] += 1LL * dp[i-1][comp+1][cost-val][nr] * comp % MOD;
                        if (dp[i][comp][cost][nr] >= MOD)
                            dp[i][comp][cost][nr] -= MOD;
                    }

                    /// creez componenta in margine

                    val = (2 * (comp-1) - (nr - 1)) * (v[i] - v[i-1]);
                    if (val <= cost && nr >= 1){
                        dp[i][comp][cost][nr] += 1LL * dp[i-1][comp-1][cost-val][nr-1] * (2 - (nr-1)) % MOD;
                        if (dp[i][comp][cost][nr] >= MOD)
                            dp[i][comp][cost][nr] -= MOD;
                    }

                    /// leg de o componenta si fixez marginea
                    val = (2 * comp - (nr - 1)) * (v[i] - v[i-1]);
                    if (val <= cost && nr >= 1){
                        dp[i][comp][cost][nr] += 1LL * dp[i-1][comp][cost-val][nr-1] * (2 - (nr-1)) % MOD;
                        if (dp[i][comp][cost][nr] >= MOD)
                            dp[i][comp][cost][nr] -= MOD;
                    }

                }

    long long sol = 0;
    for (i=0;i<=L;i++)
        sol = (sol + dp[n][1][i][2]) % MOD;

    cout<<sol;


    return 0;
}

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