oj.uz

Submission #1102723

# Submission time Handle Problem Language Result Execution time Memory
1102723 2024-10-18T18:10:58 Z ivopav Skyscraper (JOI16_skyscraper) C++17
20 / 100
 512 ms 524288 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 8 ms 4948 KB Output is correct
6 Correct 6 ms 4436 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 7 ms 4948 KB Output is correct
10 Correct 2 ms 1016 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 1628 KB Output is correct
5 Correct 3 ms 1596 KB Output is correct
6 Correct 2 ms 1616 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 2 ms 1360 KB Output is correct
10 Correct 3 ms 1360 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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 8 ms 4948 KB Output is correct
6 Correct 6 ms 4436 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 7 ms 4948 KB Output is correct
10 Correct 2 ms 1016 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 1628 KB Output is correct
15 Correct 3 ms 1596 KB Output is correct
16 Correct 2 ms 1616 KB Output is correct
17 Correct 1 ms 592 KB Output is correct
18 Correct 1 ms 848 KB Output is correct
19 Correct 2 ms 1360 KB Output is correct
20 Correct 3 ms 1360 KB Output is correct
21 Correct 8 ms 4180 KB Output is correct
22 Correct 358 ms 285520 KB Output is correct
23 Runtime error 512 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -