oj.uz

Submission #607342

# Submission time Handle Problem Language Result Execution time Memory
607342 2022-07-26T15:35:19 Z kawaii Skyscraper (JOI16_skyscraper) C++14
0 / 100
 2 ms 596 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 105
#define maxl 1005
#define int long long
const int mod=1e9+7;
int dp[2][maxn][maxl][2][2],n,a[maxn],l,t;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> l;
    for(int i=1;i<=n;i++) cin >> a[i];
    if(n == 1){
      cout << 1; return 0;
    }
    sort(a+1,a+n+1);
    for(int p=0;p<=1;p++){
        for(int q=0;q<=1;q++) dp[1][1][0][p][q]=1;
    }

    for(int i=1;i<n;i++){
        t^=1;
        for(int j=1;j<=i;j++){
            for(int k=0;k<=l;k++){
                for(int p=0;p<=1;p++){
                    for(int q=0;q<=1;q++){
                        int nk=k+(2*j-p-q)*(a[i+1]-a[i]);
                        if(nk>l) continue;
                        int v=dp[t][j][k][p][q];
                        dp[t^1][j][nk][p][q]=(dp[t^1][j][nk][p][q]+(2*j-p-q)*v)%mod;
                        dp[t^1][j-1][nk][p][q]=(dp[t^1][j-1][nk][p][q]+(j-1)*v)%mod;
                        dp[t^1][j+1][nk][p][q]=(dp[t^1][j+1][nk][p][q]+(j+1-p-q)*v)%mod;
                        if(!p){
                            dp[t^1][j][nk][1][q]=(dp[t^1][j][nk][1][q]+v)%mod;
                            dp[t^1][j+1][nk][1][q]=(dp[t^1][j+1][nk][1][q]+v)%mod;
                        }
                        if(!q){
                            dp[t^1][j][nk][p][1]=(dp[t^1][j][nk][p][1]+v)%mod;
                            dp[t^1][j+1][nk][p][1]=(dp[t^1][j+1][nk][p][1]+v)%mod;
                        }
                        dp[t][j][k][p][q]=0;
                    }
                }
            }
        }
    }
    int ans=0;t^=1;
    for(int i=0;i<=l;i++) ans=(ans+dp[t][1][i][1][1])%mod;
    if(ans < 0){
        while(1){
            
        }
    }
    cout << ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 2 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 2 ms 596 KB Output isn't correct
7 Halted 0 ms 0 KB -