Submission #1102723

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

skyscraper

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

using i64=long long int;

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

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