Submission #1102732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102732		ivopav	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	525 ms	524288 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;


using i64=long long int;

int main(){
    int n;
    int t;
    cin >> n >> t;
    if (n==1){
        cout << "1\n";
        exit(0);    
    }
    vector<vector<vector<vector<int>>>> dp(n+1,vector<vector<vector<int>>>(n+1,vector<vector<int>>(t+1,vector<int>(3,0))));
    dp[0][0][0][0]=1;
    vector<int> lis={};
    for (int i=0;i<n;i++){
        int unos;
        cin >> unos;
        lis.push_back(unos);
    }
    sort(lis.begin(),lis.end());
    lis.push_back(1e9);
    for (int i=1;i<=n;i++){
        for (int comp=1;comp<=i;comp++){
            for (int rez=0;rez<=t;rez++){
                for (int pockra=0;pockra<=2;pockra++){
                    int prom=(2*comp-pockra)*(lis[i]-lis[i-1]);

                    if (prom>rez){
                    //    cout << "- ";
                        continue;
                    }
                    if (i+comp+1-pockra>n){
                     //   cout << "- ";
                        continue;
                    }  
                    //cout << prom << " ";
                    dp[i][comp][rez][pockra]+=i64(dp[i-1][comp-1][rez-prom][pockra])%(i64(1e9+7));
                    dp[i][comp][rez][pockra]%=int (1e9+7);
                    if (pockra==1){
                        dp[i][comp][rez][pockra]+=2ll*i64(dp[i-1][comp-1][rez-prom][0])%(i64(1e9+7));
                        dp[i][comp][rez][pockra]%=int (1e9+7);
                    }
                    if (pockra==2){
                        dp[i][comp][rez][pockra]+=i64(dp[i-1][comp-1][rez-prom][1])%(i64(1e9+7));
                        dp[i][comp][rez][pockra]%=int (1e9+7);
                    }
                    dp[i][comp][rez][pockra]+=i64((comp*2-pockra))*i64(dp[i-1][comp][rez-prom][pockra])%(i64(1e9+7));
                    dp[i][comp][rez][pockra]%=int (1e9+7);
                    if (pockra==1){
                        dp[i][comp][rez][pockra]+=i64(comp*2)*i64(dp[i-1][comp][rez-prom][0])%(i64(1e9+7));
                        dp[i][comp][rez][pockra]%=int (1e9+7);
                    }
                    if (pockra==2 && i==n){
                        dp[i][comp][rez][pockra]+=i64(dp[i-1][comp][rez-prom][1])%(i64(1e9+7));
                        dp[i][comp][rez][pockra]%=int (1e9+7);
                    }
                    else if (pockra==2){
                        dp[i][comp][rez][pockra]+=i64(comp-1)*i64(dp[i-1][comp][rez-prom][1])%(i64(1e9+7));
                        dp[i][comp][rez][pockra]%=int (1e9+7);
                    }
                    if (pockra==0){
                        dp[i][comp][rez][pockra]+=i64(comp*(comp+1))*i64(dp[i-1][comp+1][rez-prom][0])%(i64(1e9+7));
                        dp[i][comp][rez][pockra]%=int (1e9+7);
                    }
                    else if (pockra==1){
                        dp[i][comp][rez][pockra]+=i64(comp*comp)*i64(dp[i-1][comp+1][rez-prom][1])%(i64(1e9+7));
                        dp[i][comp][rez][pockra]%=int (1e9+7);
                    }
                    else if (i==n){
                        dp[i][comp][rez][pockra]+=i64(dp[i-1][comp+1][rez-prom][2])%(i64(1e9+7));
                        dp[i][comp][rez][pockra]%=int (1e9+7);
                    }
                    else {
                        dp[i][comp][rez][pockra]+=i64(((comp-1)*2)+(comp-1)*(comp-2))*i64(dp[i-1][comp+1][rez-prom][2])%(i64(1e9+7));
                    }
                   // cout << dp[i][comp][rez][pockra] << " ";
                    
                }
             //   cout << "  ";
            }
           // cout << "    ";
        }
       // cout << "\n";
    }
    int rje=0;
    for (int i=0;i<=t;i++){
        rje+=dp[n][1][i][2];
        rje%=int(1e9+7);
    }
    cout << rje << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80