Submission #40725

#	Time	Username	Problem	Language	Result	Execution time	Memory
40725		bogdan10bos	Skyscraper (JOI16_skyscraper)	C++14	0 / 100	3 ms	1248 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

const int mod = 1e9 + 7;

typedef pair<int, int> pii;
typedef pair<pii, pii> p4i;

int N, L;
int v[105];
int dp[105][105][1005][3];
bool inq[105][105][1005][3];
/// dp[i][j][k][e] - first i numbers, j remaining gaps, k cost, e ends are fixed
queue<p4i> q;

void addto(int x, int y, int z, int e, int vl)
{
    if(x < 0 || y < 0 || z < 0 || e < 0)    return;
    if(z > L)   return;
    if(vl == 0) return;
    if(y == 1 && e == 0)    return;
    if(y == 0 && e <= 1)    return;
    if(x != N && y == 0)    return;

    dp[x][y][z][e] += vl;
    if(dp[x][y][z][e] >= mod)   dp[x][y][z][e] -= mod;
    if(!inq[x][y][z][e])
    {
        q.push( { {x, y}, {z, e} } );
        inq[x][y][z][e] = 1;
    }
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &L);
    for(int i = 1; i <= N; i++) scanf("%d", &v[i]);
    sort(v + 1, v + N + 1);

    dp[1][2][0][0] = 1; q.push({ {1, 2}, {0, 0} });
    dp[1][1][0][1] = 2; q.push({ {1, 1}, {0, 1} });

    int ans = 0;
    while(!q.empty())
    {
        auto x = q.front();
        q.pop();

        int i = x.first.first;
        int j = x.first.second;
        int k = x.second.first;
        int e = x.second.second;

        int nk = k + (v[i + 1] - v[i]) * (2 * j - 2 + e);
        int vl = dp[i][j][k][e];

        if(i == N)
        {
            if(j == 0 && e == 2 && k <= L)
                (ans += dp[i][j][k][e]) %= mod;
            continue;
        }

        /// middle, no fix
        addto(i + 1, j + 1, nk, e, (1LL * vl * j) % mod);
        /// middle, 1 fix, 1 free
        addto(i + 1, j, nk, e, (1LL * vl * (j * 2 - 2 + e)) % mod);
        /// middle, 2 fix
        addto(i + 1, j - 1, nk, e, (1LL * vl * j) % mod);

        if(e == 0)
        {
            /// end, no fix
            addto(i + 1, j, nk, e + 1, (2 * vl) % mod);
            /// end, fix
            addto(i + 1, j - 1, nk, e + 1, (2 * vl) % mod);
        }
        else if(e == 1)
        {
            /// end, no fix
            addto(i + 1, j, nk, e + 1, vl);
            /// end, fix
            addto(i + 1, j - 1, nk, e + 1, vl);
        }
    }

    printf("%d\n", ans);

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:44:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &L);
                          ^
skyscraper.cpp:45:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%d", &v[i]);
                                                   ^

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