oj.uz

Submission #1102721

# Submission time Handle Problem Language Result Execution time Memory
1102721 2024-10-18T18:07:45 Z ivopav Skyscraper (JOI16_skyscraper) C++17
15 / 100
 3 ms 1788 KB 
#include <bits/stdc++.h>
using namespace std;

using i64=long long int;

int main(){
    i64 n;
    i64 t;
    cin >> n >> t;
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1016 KB Output is correct
2 Correct 3 ms 1620 KB Output is correct
3 Correct 2 ms 852 KB Output is correct
4 Correct 3 ms 1788 KB Output is correct
5 Correct 3 ms 1620 KB Output is correct
6 Correct 3 ms 1620 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 2 ms 1364 KB Output is correct
10 Correct 2 ms 1364 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -