oj.uz

Submission #516701

# Submission time Handle Problem Language Result Execution time Memory
516701 2022-01-21T23:51:37 Z rodov Skyscraper (JOI16_skyscraper) C++14
100 / 100
 147 ms 77204 KB 
#include <bits/stdc++.h>

using namespace std;

long long n,L,res,diff;
long long d[107][107][1007][3];
long long a[107];
const long long MOD = 1e9+7;

int main() {
    cin >> n >> L;
    for(int i=1; i<=n; i++) cin >> a[i];
    if(n==1) { cout << 1 << endl; return 0; }
    a[n+1]=10000;
    sort(a+1, a+1+n);
    d[0][0][0][0] = 1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i; j++)
            for(int k=0; k<=L; k++)
                for(int m=0; m<=2; m++) {
                    diff = (2*j-m)*(a[i+1]-a[i]);
                    if(k-diff<0) continue;
                    d[i][j][k][m] += (d[i-1][j+1][k-diff][m] * j)%MOD;
                    d[i][j][k][m] += (d[i-1][j-1][k-diff][m] * (j-m)) %MOD;
                    d[i][j][k][m] += (d[i-1][j][k-diff][m] * (2*j-m))%MOD;
                    if(m>0) d[i][j][k][m] += (d[i-1][j-1][k-diff][m-1] * (3-m))%MOD;
                    if(m>0) d[i][j][k][m] += (d[i-1][j][k-diff][m-1] *(3-m) )%MOD;

                    d[i][j][k][m] %= MOD;
                }
    res = 0;
    for(int k=0; k<=L; k++) res += d[n][1][k][2];
    res %= MOD;
    cout << res << endl;

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 684 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 812 KB Output is correct
10 Correct 1 ms 460 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 684 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 2 ms 808 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 684 KB Output is correct
9 Correct 1 ms 812 KB Output is correct
10 Correct 1 ms 680 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 684 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 812 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 716 KB Output is correct
13 Correct 1 ms 716 KB Output is correct
14 Correct 1 ms 684 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Correct 2 ms 808 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 684 KB Output is correct
19 Correct 1 ms 812 KB Output is correct
20 Correct 1 ms 680 KB Output is correct
21 Correct 3 ms 3116 KB Output is correct
22 Correct 119 ms 65560 KB Output is correct
23 Correct 130 ms 76568 KB Output is correct
24 Correct 132 ms 74916 KB Output is correct
25 Correct 143 ms 77088 KB Output is correct
26 Correct 147 ms 71828 KB Output is correct
27 Correct 55 ms 41304 KB Output is correct
28 Correct 61 ms 47708 KB Output is correct
29 Correct 109 ms 72680 KB Output is correct
30 Correct 132 ms 77204 KB Output is correct