oj.uz

Submission #971949

# Submission time Handle Problem Language Result Execution time Memory
971949 2024-04-29T14:55:33 Z 12345678 Skyscraper (JOI16_skyscraper) C++17
15 / 100
 9 ms 31248 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=105, mx=1005, mod=1e9+7;

#define ll long long

ll n, m, h[nx], dp[nx][nx][mx][3], res, c;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>h[i];
    sort(h+1, h+n+1);
    dp[0][0][0][0]=1;
    for (int i=1; i<n; i++)
    {
        for (int j=1; j<=i; j++)
        {
            for (int k=0; k<=m; k++)
            {
                for (int l=0; l<3; l++)
                {
                    ll x=(h[i+1]-h[i])*(2*j-l);
                    if (k<x) continue;
                    dp[i][j][k][l]=dp[i-1][j-1][k-x][l];
                    if (l>0) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j-1][k-x][l-1]*(3-l))%mod;
                    dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j][k-x][l]*(2*j-l))%mod;
                    if (l>0) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j][k-x][l-1]*(3-l)*(j-(l-1)))%mod;
                    if (l==0) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j+1][k-x][l]*(j+1)*j)%mod;
                    if (l==1) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j+1][k-x][l]*j*j)%mod;
                    if (l==2) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i-1][j+1][k-x][l]*j*(j-1))%mod;
                }
            }
        }
    }
    for (int i=0; i<=m; i++) res=(res+dp[n-1][2][i][2]+dp[n-1][1][i][1])%mod;
    cout<<res;
}

/*
4 2
1 2 3 4
*/

Subtask #1
0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26972 KB Output is correct
2 Correct 8 ms 31068 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 4 ms 31068 KB Output is correct
5 Correct 5 ms 31068 KB Output is correct
6 Correct 4 ms 31192 KB Output is correct
7 Correct 5 ms 31068 KB Output is correct
8 Correct 4 ms 31064 KB Output is correct
9 Correct 4 ms 31068 KB Output is correct
10 Correct 5 ms 31248 KB Output is correct

Subtask #3
0 / 80.0

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