Submission #40727

#	Time	Username	Problem	Language	Result	Execution time	Memory
40727		bogdan10bos	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	146 ms	18720 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 == 3 && y == 1 && z == 4 && e == 1)
    {
        x++;
        x--;
    }

    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;
    if(y > N - x)
        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;
    }
}

void brute(int v[])
{
    vector<int> p;
    for(int i = 1; i <= N; i++) p.push_back(v[i]);
    vector< vector<int> > pp[105];

    sort(p.begin(), p.end());

    int ans = 0;
    do
    {
        int cnt = 0;
        for(int i = 1; i < p.size(); i++)
            cnt += abs(p[i] - p[i - 1]);
        if(cnt <= L)    ans++;
    }while(next_permutation(p.begin(), p.end()));
    printf("%d\n", ans);
}

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);

    if(N <= 8)
    {
        brute(v);
        exit(0);
    }

    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(nk > L)  continue;

        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 - 2 + e)) % 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 'void brute(int*)':
skyscraper.cpp:57:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 1; i < p.size(); i++)
                          ^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:71: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:72: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: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80