oj.uz

Submission #476063

# Submission time Handle Problem Language Result Execution time Memory
476063 2021-09-24T17:07:03 Z nicolaalexandra Skyscraper (JOI16_skyscraper) C++14
100 / 100
 402 ms 84144 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 1 ms 552 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 1 ms 588 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 2 ms 972 KB Output is correct
6 Correct 2 ms 1100 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 2 ms 1228 KB Output is correct
10 Correct 1 ms 972 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 1 ms 552 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 972 KB Output is correct
12 Correct 1 ms 972 KB Output is correct
13 Correct 1 ms 1100 KB Output is correct
14 Correct 1 ms 972 KB Output is correct
15 Correct 2 ms 972 KB Output is correct
16 Correct 2 ms 1100 KB Output is correct
17 Correct 1 ms 844 KB Output is correct
18 Correct 1 ms 1100 KB Output is correct
19 Correct 2 ms 1228 KB Output is correct
20 Correct 1 ms 972 KB Output is correct
21 Correct 4 ms 3880 KB Output is correct
22 Correct 336 ms 71708 KB Output is correct
23 Correct 402 ms 68820 KB Output is correct
24 Correct 338 ms 78152 KB Output is correct
25 Correct 401 ms 71268 KB Output is correct
26 Correct 347 ms 69936 KB Output is correct
27 Correct 143 ms 57872 KB Output is correct
28 Correct 183 ms 64300 KB Output is correct
29 Correct 327 ms 84144 KB Output is correct
30 Correct 388 ms 70576 KB Output is correct