oj.uz

Submission #40725

# Submission time Handle Problem Language Result Execution time Memory
40725 2018-02-07T13:02:15 Z bogdan10bos Skyscraper (JOI16_skyscraper) C++14
0 / 100
 3 ms 1248 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -