oj.uz

Submission #1102729

# Submission time Handle Problem Language Result Execution time Memory
1102729 2024-10-18T18:19:11 Z ivopav Skyscraper (JOI16_skyscraper) C++17
20 / 100
 403 ms 285512 KB 
#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]);
                    prom%=int (1e9+7);
                    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];
                    dp[i][comp][rez][pockra]%=int (1e9+7);
                    if (pockra==1){
                        dp[i][comp][rez][pockra]+=2*dp[i-1][comp-1][rez-prom][0];
                        dp[i][comp][rez][pockra]%=int (1e9+7);
                    }
                    if (pockra==2){
                        dp[i][comp][rez][pockra]+=dp[i-1][comp-1][rez-prom][1];
                        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]+=dp[i-1][comp][rez-prom][1];
                        dp[i][comp][rez][pockra]%=int (1e9+7);
                    }
                    else if (pockra==2){
                        dp[i][comp][rez][pockra]+=i64(comp-1)%(int(1e9+7))*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))%(int(1e9+7))*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)%(int(1e9+7))*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]+=dp[i-1][comp+1][rez-prom][2];
                        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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 6 ms 5152 KB Output is correct
6 Correct 6 ms 4432 KB Output is correct
7 Correct 2 ms 1104 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 7 ms 4944 KB Output is correct
10 Correct 1 ms 848 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 848 KB Output is correct
2 Correct 2 ms 1616 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Correct 2 ms 1616 KB Output is correct
5 Correct 3 ms 1616 KB Output is correct
6 Correct 3 ms 1616 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 2 ms 1528 KB Output is correct
10 Correct 2 ms 1528 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 6 ms 5152 KB Output is correct
6 Correct 6 ms 4432 KB Output is correct
7 Correct 2 ms 1104 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 7 ms 4944 KB Output is correct
10 Correct 1 ms 848 KB Output is correct
11 Correct 2 ms 848 KB Output is correct
12 Correct 2 ms 1616 KB Output is correct
13 Correct 2 ms 848 KB Output is correct
14 Correct 2 ms 1616 KB Output is correct
15 Correct 3 ms 1616 KB Output is correct
16 Correct 3 ms 1616 KB Output is correct
17 Correct 1 ms 848 KB Output is correct
18 Correct 2 ms 848 KB Output is correct
19 Correct 2 ms 1528 KB Output is correct
20 Correct 2 ms 1528 KB Output is correct
21 Correct 8 ms 4176 KB Output is correct
22 Incorrect 403 ms 285512 KB Output isn't correct
23 Halted 0 ms 0 KB -