oj.uz

Submission #94598

# Submission time Handle Problem Language Result Execution time Memory
94598 2019-01-21T15:30:12 Z Bliss_of_comprehension Skyscraper (JOI16_skyscraper) C++14
15 / 100
 4 ms 1912 KB 
#include <bits/stdc++.h>
#define mod 1000000007

using namespace std;

typedef long long ll;

ll dp[105][105][1005][2][2]={};

int main(){
    int n,l;
    cin >> n >> l;
    vector <int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    dp[0][0][0][0][0]=1;
    ll ans=0;
    for(int i=0;i<n;i++){
        if(i==n-1){
            for(int k=0;k<=l;k++){
                for(int iss=0;iss<2;iss++){
                    for(int ise=0;ise<2;ise++){
                        dp[i][0][k][iss][ise]%=mod;
                        if(iss+ise>0)
                            ans=(ans+dp[i][0][k][iss][ise])%mod;
                    }
                }

            }
            continue;
        }

        for(int j=0;j<=n;j++){
            for(int k=0;k<=l;k++){
                for(int iss=0;iss<2;iss++){
                    for(int ise=0;ise<2;ise++){
//                        if(i==2){
//                            cout << i << " " << j << " " << k << " " << iss << " " << ise << " " << dp[i][j][k][iss][ise] << endl;
//                        }
                        ll &cur = dp[i][j][k][iss][ise];
                        assert(cur>=0);
                        cur%=mod;
                        int diff = a[i+1]-a[i];
                        int nl=k+(a[i+1]-a[i])*(2*j+iss+ise);
                        if(j){
                            if(nl-2*diff>l){
                                continue;
                            }
                            if(iss){
                                dp[i+1][j-1][nl-2*diff][iss][ise]+=cur*j;
                            }
                            if(ise){
                                dp[i+1][j-1][nl-2*diff][iss][ise]+=cur*j;
                            }
                            if(j>1){
                                dp[i+1][j-1][nl-2*diff][iss][ise]+=cur*j*(j-1);
                            }
                            if(nl-diff>l){
                                continue;
                            }
                            if(!iss){
                                dp[i+1][j-1][nl-diff][1][ise]+=cur*j;
                            }
                            if(!ise){
                                dp[i+1][j-1][nl-diff][iss][1]+=cur*j;
                            }
                        }

                        if(nl>l){
                            continue;
                        }
                        if(iss){
                            dp[i+1][j][nl][iss][ise]+=cur;
                        }
                        if(ise){
                            dp[i+1][j][nl][iss][ise]+=cur;
                        }
                        if(j){
                            dp[i+1][j][nl][iss][ise]+=(2*j)*cur;
                        }
                        if(nl+diff>l){
                            continue;
                        }
                        if(!iss){
                            dp[i+1][j][nl+diff][1][ise]+=cur;
                        }
                        if(!ise){
                            dp[i+1][j][nl+diff][iss][1]+=cur;
                        }
                        if(nl+2*diff>l){
                            continue;
                        }
                        dp[i+1][j+1][nl+2*diff][iss][ise]+=cur;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 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 3 ms 1272 KB Output is correct
2 Correct 4 ms 1784 KB Output is correct
3 Correct 3 ms 1528 KB Output is correct
4 Correct 4 ms 1784 KB Output is correct
5 Correct 4 ms 1912 KB Output is correct
6 Correct 3 ms 1784 KB Output is correct
7 Correct 3 ms 1272 KB Output is correct
8 Correct 3 ms 1528 KB Output is correct
9 Correct 3 ms 1784 KB Output is correct
10 Correct 3 ms 1656 KB Output is correct

Subtask #3
0 / 80.0

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