oj.uz

Submission #587093

# Submission time Handle Problem Language Result Execution time Memory
587093 2022-07-01T09:56:34 Z Jarif_Rahman Skyscraper (JOI16_skyscraper) C++17
15 / 100
 222 ms 475948 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const ll md = 1e9+7;
const int lim = 2005;

ll dp[100][101][lim][3];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for(int i = 0; i < 100; i++) for(int j = 0; j <= 100; j++)
        for(int k = 0; k < lim; k++) for(int l = 0; l < 3; l++) dp[i][j][k][l] = 0;

    int n, L; cin >> n >> L;
    vector<int> A(n);
    for(int &x: A) cin >> x;
    sort(A.begin(), A.end());

    auto d = [&](int i, int j, int m){
        return (2*j-m)*(A[i]-A[i-1]);
    };

    dp[0][1][0][0] = 1;
    dp[0][1][0][1] = 2;
    
    for(int i = 1; i < n; i++) for(int j = 1; j <= i+1; j++)
    for(int c = 0; c < lim; c++) for(int m = 0; m <= 2; m++){
        //-
        if(c-d(i,j-1,m) >= 0 && j > 1)
            dp[i][j][c][m]+=dp[i-1][j-1][c-d(i,j-1,m)][m], dp[i][j][c][m]%=md;

        //:-
        if(c-d(i,j-1,m-1) >= 0 && j > 1 && m > 0){
            if(j == 1 && i == n-1 && m == 2)
                dp[i][j][c][m]+=dp[i-1][j-1][c-d(i,j-1,m-1)][m-1], dp[i][j][c][m]%=md;
            else if(j != 1)
                dp[i][j][c][m]+=(dp[i-1][j-1][c-d(i,j-1,m-1)][m-1]*(3-m))%md, dp[i][j][c][m]%=md;
        }

        //---- + - = -----
        if(c-d(i,j,m) >= 0)
            dp[i][j][c][m]+=(dp[i-1][j][c-d(i,j,m)][m]*(2*j-m))%md, dp[i][j][c][m]%=md;

        //---- + -: = -----:
        if(c-d(i,j,m-1) >= 0 && m > 0){
            if(i == n-1 && j == 1 && m == 2)
                dp[i][j][c][m]+=dp[i-1][j][c-d(i,j,m-1)][m-1], dp[i][j][c][m]%=md;
            else if(m == 1)
                dp[i][j][c][m]+=(dp[i-1][j][c-d(i,j,m-1)][m-1]*2*j)%md, dp[i][j][c][m]%=md;
            else if(j != 1)
                dp[i][j][c][m]+=(dp[i-1][j][c-d(i,j,m-1)][m-1]*(j-1))%md, dp[i][j][c][m]%=md;
        }

        //---- + - + ---- = ---------
        if(c-d(i,j+1,m) >= 0 && j+1 <= i){
            if(i == n-1 && j == 1 && m == 2)
                dp[i][j][c][m]+=dp[i-1][j+1][c-d(i,j+1,m)][m], dp[i][j][c][m]%=md;
            else if(m == 0)
                dp[i][j][c][m]+=(dp[i-1][j+1][c-d(i,j+1,m)][m]*j*(j+1))%md, dp[i][j][c][m]%=md;
            else if(m == 1)
                dp[i][j][c][m]+=(dp[i-1][j+1][c-d(i,j+1,m)][m]*j*j)%md, dp[i][j][c][m]%=md;
            else if(j != 1)
                dp[i][j][c][m]+=(dp[i-1][j+1][c-d(i,j+1,m)][m]*j*(j-1))%md, dp[i][j][c][m]%=md;
        }
    }

    ll ans = 0;

    for(int i = 0; i <= L; i++) ans+=dp[n-1][1][i][2], ans%=md;

    cout << ans << "\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 475852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 475820 KB Output is correct
2 Correct 209 ms 475724 KB Output is correct
3 Correct 220 ms 475732 KB Output is correct
4 Correct 205 ms 475728 KB Output is correct
5 Correct 203 ms 475800 KB Output is correct
6 Correct 198 ms 475724 KB Output is correct
7 Correct 199 ms 475848 KB Output is correct
8 Correct 199 ms 475804 KB Output is correct
9 Correct 201 ms 475948 KB Output is correct
10 Correct 201 ms 475828 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 475852 KB Output isn't correct
2 Halted 0 ms 0 KB -