oj.uz

Submission #1118087

# Submission time Handle Problem Language Result Execution time Memory
1118087 2024-11-24T23:14:42 Z huseynahmadli2010 Skyscraper (JOI16_skyscraper) C++17
100 / 100
 97 ms 80860 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int sz=2e5+5;

const int INF=1e18;

const int MOD=1e9+7;

int dp[105][105][1005][5];

int arr[sz];

void solve()
{
    int n,l;
    
    cin>>n>>l;
    
    for(int i=1;i<=n;i++)
        cin>>arr[i];
    
    if(n==1)
    {
        cout<<1;
        
        return;
    }
    
    sort(arr+1,arr+n+1);
    
    arr[n+1]=10000;
    
    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<=l;k++)
            {
                for(int m=0;m<3;m++)
                {
                    int cur=(2*j-m)*(arr[i+1]-arr[i]);
                    
                    if(cur>k || i+j+1-m>n)
                        continue;
                    
                    dp[i][j][k][m]+=dp[i-1][j-1][k-cur][m];
                    
                    if(m)
                        dp[i][j][k][m]+=(3-m)*dp[i-1][j-1][k-cur][m-1];
                    
                    dp[i][j][k][m]+=(2*j-m)*dp[i-1][j][k-cur][m];
                    
                    if(m==1)
                        dp[i][j][k][m]+=2*j*dp[i-1][j][k-cur][m-1];
                    
                    else if(m==2)
                    {
                        if(i==n)
                            dp[i][j][k][m]+=dp[i-1][j][k-cur][m-1];
                        
                        else if(j>1)
                            dp[i][j][k][m]+=(j-1)*dp[i-1][j][k-cur][m-1];
                    }
                    
                    if(m==1)
                        dp[i][j][k][m]+=j*j*dp[i-1][j+1][k-cur][m];
                    
                    else if(m==2)
                    {
                        if(i==n)
                            dp[i][j][k][m]+=dp[i-1][j+1][k-cur][m];
                        
                        else
                            dp[i][j][k][m]+=j*(j-1)*dp[i-1][j+1][k-cur][m];
                    }
                    
                    else
                        dp[i][j][k][m]+=j*(j+1)*dp[i-1][j+1][k-cur][m];
                    
                    dp[i][j][k][m]%=MOD;
                }
            }
        }
    }
    
    int res=0;
    
    for(int i=0;i<=l;i++)
        res+=dp[n][1][i][2];
    
    cout<<res%MOD;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
    
    //cin>>t;
    
    while(t--)
    {
        solve();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 2 ms 1104 KB Output is correct
10 Correct 1 ms 592 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1 ms 848 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 1 ms 848 KB Output is correct
6 Correct 1 ms 848 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 848 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 1104 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 2 ms 1104 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 1 ms 848 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 848 KB Output is correct
15 Correct 1 ms 848 KB Output is correct
16 Correct 1 ms 848 KB Output is correct
17 Correct 1 ms 592 KB Output is correct
18 Correct 1 ms 592 KB Output is correct
19 Correct 2 ms 724 KB Output is correct
20 Correct 1 ms 848 KB Output is correct
21 Correct 3 ms 2640 KB Output is correct
22 Correct 61 ms 55112 KB Output is correct
23 Correct 91 ms 75336 KB Output is correct
24 Correct 80 ms 71116 KB Output is correct
25 Correct 94 ms 80712 KB Output is correct
26 Correct 85 ms 70116 KB Output is correct
27 Correct 34 ms 32328 KB Output is correct
28 Correct 40 ms 37960 KB Output is correct
29 Correct 72 ms 61692 KB Output is correct
30 Correct 97 ms 80860 KB Output is correct