Submission #205989

#	Time	Username	Problem	Language	Result	Execution time	Memory
205989		stefdasca	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	109 ms	23928 KiB

skyscraper

#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;


int add(int a, int b)
{
    int x = a+b;
    if(x >= mod)
        x -= mod;
    if(x < 0)
        x += mod;
    return x;
}
ll mul(ll a, ll b)
{
    return (a*b) % mod;
}

ll pw(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand_seed()
{
    long long a = rng();
    return a;
}

ll dp[101][101][1001][3];
/*
    dp[i][j][k][l] :
    i - number of numbers placed
    j - number of connected components
    k - total sum currently (filling empty spaces with a_{i} (0-indexed)
    l - number of endpoints that are filled
*/
ll v[101];
int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, l;
    cin >> n >> l;
    for(int i = 0; i < n; i++)
        cin >> v[i];
    sort(v, v + n);
    if(n == 1)
    {
        cout << 1;
        return 0;
    }
    v[n] = (1<<20);
    if(v[1] - v[0] <= l)
        dp[1][1][v[1] - v[0]][1] = 2; //fill a[0] at one of the endpoints, there are 2 endpoints to fill.
    if(2 * (v[1] - v[0]) <= l)
        dp[1][1][2 * (v[1] - v[0])][0] = 1; //fill a[0] in the middle, positions doesn't matter.
    for(int i = 1; i < n; i++)
        for(int j = 1; j <= i; j++)
            for(int k = 0; k <= l; k++)
                for(int z = 0; z < 3; z++)
                {
                    if(!dp[i][j][k][z])
                        continue;
                    int diff = v[i + 1] - v[i];
                    //First, we try to fill one of the ends
                    if(z < 2 && k + diff * (2 * j - z - 1) <= l) //there are 2*j - z - 1 positions that we're supposed to "upgrade" (-1 because one of the positions is merged with the endpoints after this move)
                    {
                        if(i == n - 1)
                            dp[i + 1][j][k + diff * (2 * j - z - 1)][z + 1] = add(dp[i + 1][j][k + diff * (2 * j - z - 1)][z + 1], mul(dp[i][j][k][z], (2-z) * j)); //we have j con. comp. to choose to merge with
                        else
                            if(z == 0 || j > 1) //otherwise this coincides with i == n - 1
                                dp[i + 1][j][k + diff * (2 * j - z - 1)][z + 1] = add(dp[i + 1][j][k + diff * (2 * j - z - 1)][z + 1], mul(dp[i][j][k][z], (2-z)*(j-z))); //can only merge with the con comp. that are not connected to ends.
                        if(k + diff * (2 * j - z + 1) <= l) //now we create a new cc.
                            dp[i + 1][j + 1][k + diff * (2 * j - z + 1)][z + 1] = add(dp[i + 1][j + 1][k + diff * (2 * j - z + 1)][z + 1], mul(dp[i][j][k][z], (2-z))); //we can choose one of the ends to create
                    }
                    //Next, we dont fill the ends.
                    //Part 1 : Create new cc
                    if(k + diff*(2*j - z + 2) <= l) //2 new positions to "upgrade"
                    {
                        dp[i + 1][j + 1][k + diff*(2*j - z + 2)][z] = add(dp[i + 1][j + 1][k + diff*(2*j - z + 2)][z], dp[i][j][k][z]); //nothing new happens
                    }
                    //Part 2 : Stick to one cc
                    if(k + diff*(2*j - z) <= l) //no new positions to "upgrade"
                    {
                        dp[i + 1][j][k + diff*(2*j - z)][z] = add(dp[i + 1][j][k + diff*(2*j - z)][z], mul(dp[i][j][k][z], (2*j - z))); //we can merge in 2*j - z possible positions
                    }
                    //Part 3 : Merge two ccs together
                    if((k + diff*(2*j - z - 2) <= l) && (j >= 2) && (i == n - 1 || j > 2 || z < 2))
                    {
                        if(z == 0)
                        {
                            dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] = add(dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z], mul(dp[i][j][k][z], j*(j-1))); //there are jP2 possible merges
                        }
                        if(z == 1)
                        {
                            dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] = add(dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z], mul(dp[i][j][k][z], (j-1)*(j-1))); //there are (j-1)P2+(j-1) merges
                        }
                        if(z == 2)
                        {
                            if(i == n - 1)
                            {
                                dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] = add(dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z], dp[i][j][k][z]); //there's only 1 place it can go.
                            }
                            else
                            {
                                dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] = add(dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z], mul(dp[i][j][k][z], (j-2)*(j-1))); //there're (j-2)P2 + 2(j-2) possiblilities
                            }
                        }
                    }
                }
    ll answer = 0;
    for(int i = 0; i <= l; i++)
        answer = add(answer, dp[n][1][i][2]);
    cout << answer << '\n';
    return 0;
}

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