Submission #587093

#	Time	Username	Problem	Language	Result	Execution time	Memory
587093		Jarif_Rahman	Skyscraper (JOI16_skyscraper)	C++17	15 / 100	222 ms	475948 KiB

skyscraper

#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
• Subtask 2: 15 / 15
• Subtask 3: 0 / 80