oj.uz

답안 #442306

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
442306 2021-07-07T12:21:54 Z Pajaraja Skyscraper (JOI16_skyscraper) C++17
15 / 100
 35 ms 1480 KB 
#include <bits/stdc++.h>
#define MAXN 107
#define MAXL 1007
#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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1448 KB Output is correct
2 Correct 26 ms 1452 KB Output is correct
3 Correct 33 ms 1452 KB Output is correct
4 Correct 26 ms 1460 KB Output is correct
5 Correct 26 ms 1476 KB Output is correct
6 Correct 28 ms 1356 KB Output is correct
7 Correct 28 ms 1480 KB Output is correct
8 Correct 28 ms 1476 KB Output is correct
9 Correct 35 ms 1356 KB Output is correct
10 Correct 26 ms 1356 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 844 KB Output isn't correct
2 Halted 0 ms 0 KB -