Submission #503084

#	Time	Username	Problem	Language	Result	Execution time	Memory
503084		qwerasdfzxcl	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	228 ms	197812 KiB

skyscraper

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int MOD = 1e9+7;
ll dp[102][102][3][1002], a[102];

inline void add(ll &x, ll y){
    x += y;
    if (x>=MOD) x -= MOD;
}

int main(){
    int n, L;
    scanf("%d %d", &n, &L);
    for (int i=1;i<=n;i++) scanf("%lld", a+i);
    if (n==1) {printf("1\n"); return 0;}
    sort(a+1, a+n+1);

    dp[n-1][0][1][(a[n]-a[n-1])] = 1;
    if (a[n]-a[n-1]*2<=L) dp[n-1][0][2][(a[n]-a[n-1])*2] = 1;

    for (int i=n-2;i;i--){
        for (int j=0;j<=n;j++){
            int val0 = (a[i+1] - a[i]) * (j*2);
            int val1 = (a[i+1] - a[i]) * (j*2 + 1);
            int val2 = (a[i+1] - a[i]) * (j*2 + 2);

            if (j){
            for (int k=val0;k<=L;k++){
                add(dp[i][j][0][k], dp[i+1][j+1][0][k-val0] * (j+1) %MOD);
                add(dp[i][j][0][k], dp[i+1][j][0][k-val0] * (j*2) %MOD);
                add(dp[i][j][0][k], dp[i+1][j-1][0][k-val0] * (j-1) %MOD);

                add(dp[i][j][0][k], dp[i+1][j][1][k-val0] *2 %MOD);
                add(dp[i][j][0][k], dp[i+1][j-1][1][k-val0] *2 %MOD);
            }}

            for (int k=val1;k<=L;k++){
                add(dp[i][j][1][k], dp[i+1][j+1][1][k-val1] * (j+1) %MOD);
                add(dp[i][j][1][k], dp[i+1][j][1][k-val1] * (j*2+1) %MOD);
                if (j) add(dp[i][j][1][k], dp[i+1][j-1][1][k-val1] * j %MOD);

                add(dp[i][j][1][k], dp[i+1][j][2][k-val1]);
                if (j) add(dp[i][j][1][k], dp[i+1][j-1][2][k-val1]);
            }

            for (int k=val2;k<=L;k++){
                add(dp[i][j][2][k], dp[i+1][j+1][2][k-val2] * (j+1) %MOD);
                add(dp[i][j][2][k], dp[i+1][j][2][k-val2] * (j*2+2) %MOD);
                if (j) add(dp[i][j][2][k], dp[i+1][j-1][2][k-val2] * (j+1) %MOD);
            }
        }
    }

    ll ans = 0;
    for (int k=0;k<=L;k++){
        add(ans, dp[1][1][0][k]);
        add(ans, dp[1][0][1][k]*2%MOD);

        //if (k<=10) printf("%d %d\n", dp[1][1][0][k], dp[1][0][1][k]);
    }

    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d %d", &n, &L);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:16:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     for (int i=1;i<=n;i++) scanf("%lld", a+i);
      |                            ~~~~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80