oj.uz

Submission #442307

# Submission time Handle Problem Language Result Execution time Memory
442307 2021-07-07T12:23:15 Z Pajaraja Skyscraper (JOI16_skyscraper) C++17
15 / 100
 58 ms 2756 KB 
#include <bits/stdc++.h>
#define MAXN 107
#define MAXL 2007
#define LAYERS 25
#define MOD 1000000007
using namespace std;
long long dp[2][LAYERS][MAXL][3],a[MAXN];
int main()
{
    int n; long long lim; cin>>n>>lim;
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n); a[n]=a[n-1];
    dp[n&1][0][0][0]=1;
    for(int i=n-1;i>=0;i--)
    {
        int l=i&1;
        for(int j=0;j<LAYERS;j++) for(int k=0;k<MAXL;k++) for(int g=0;g<3;g++)
        {
            dp[l][j][k][g]=0;
            if(i<n-1 && k-(2*j-g)*(a[i+1]-a[i])>=0) dp[l][j][k][g]=(dp[l][j][k][g]+dp[l^1][j][k-(2*j-g)*(a[i+1]-a[i])][g]*(2*j-g))%MOD;
            if(j>0 && k-(2*j-2-g)*(a[i+1]-a[i])>=0) dp[l][j][k][g]=(dp[l][j][k][g]+dp[l^1][j-1][k-(2*j-2-g)*(a[i+1]-a[i])][g])%MOD;
            if((j>1 || g<2) && j+1<LAYERS && k-(2*j+2-g)*(a[i+1]-a[i])>=0) dp[l][j][k][g]=(dp[l][j][k][g]+dp[l^1][j+1][k-(2*j+2-g)*(a[i+1]-a[i])][g]*(j+1-(g+1)/2)*(j-g/2))%MOD;
            if(g>0 && j>0 && k-(2*j-1-g)*(a[i+1]-a[i])>=0) dp[l][j][k][g]=(dp[l][j][k][g]+dp[l^1][j-1][k-(2*j-1-g)*(a[i+1]-a[i])][g-1])%MOD;
            if((j>1 || g<2) && g>0 && k-(2*j+1-g)*(a[i+1]-a[i])>=0) dp[l][j][k][g]=(dp[l][j][k][g]+dp[l^1][j][k-(2*j+1-g)*(a[i+1]-a[i])][g-1]*(j+1-g))%MOD;
        }
    }
    for(int k=0;k<MAXL;k++) if(k-2*(a[1]-a[0])>=0) dp[0][1][k][2]=(dp[0][1][k][2]+dp[1][2][k-2*(a[1]-a[0])][2])%MOD;
    for(int k=0;k<MAXL;k++) if(k-1*(a[1]-a[0])>=0) dp[0][1][k][2]=(dp[0][1][k][2]+dp[1][1][k-1*(a[1]-a[0])][1])%MOD;
    long long sol=0;
    for(int k=0;k<=lim;k++) sol=(sol+2*dp[0][1][k][2])%MOD;
    cout<<sol;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1424 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 48 ms 2624 KB Output is correct
2 Correct 53 ms 2624 KB Output is correct
3 Correct 57 ms 2608 KB Output is correct
4 Correct 56 ms 2636 KB Output is correct
5 Correct 54 ms 2636 KB Output is correct
6 Correct 57 ms 2624 KB Output is correct
7 Correct 58 ms 2636 KB Output is correct
8 Correct 56 ms 2636 KB Output is correct
9 Correct 57 ms 2636 KB Output is correct
10 Correct 56 ms 2756 KB Output is correct

Subtask #3
0 / 80.0

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