Submission #1188929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188929		altern23	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	114 ms	81824 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
typedef pair<ll,ll> pii;

const int MAXN = 1e2+5, MAXL = 1e3 + 5, MOD = 1e9+7;

int N, L;
ll a[MAXN], dp[MAXN][MAXN][MAXL][3];

void add(ll &a, ll b) { a = (a + b) % MOD; }

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> L;
    for(int i = 1; i <= N; i++) cin >> a[i];
    if(N == 1){
      cout << 1 << "\n";
      return 0;
    }
    
    sort(a + 1, a + 1 + N);
    
    dp[1][1][0][0] = 1, dp[1][1][0][1] = 2;
    
    ll ans = 0;
    for(int i = 1; i < N; i++){
      for(int j = 1; j <= i; j++){
        for(int k = 0; k <= L; k++){
          for(int e = 0; e < 3; e++){
            int f = (2 * j - e) * (a[i + 1] - a[i]);
            if(k + f <= L){
              add(dp[i + 1][j + 1][k + f][e], dp[i][j][k][e] * (j + 1 - e));
              if(e < 2) add(dp[i + 1][j + 1][k + f][e + 1], dp[i][j][k][e] * (2 - e));
              add(dp[i + 1][j][k + f][e], dp[i][j][k][e] * (2 * j - e));
              if(e < 2) add(dp[i + 1][j][k + f][e + 1], dp[i][j][k][e] * (2 - e));
              add(dp[i + 1][j - 1][k + f][e], dp[i][j][k][e] * (j - 1));
            }
          }
        }
      }
    }
    
    for(int i = 0; i <= L; i++) add(ans, dp[N][1][i][2]);
    cout << ans << "\n";
}

/*
C+1
C+1 ujung
C
C ujung
C-1
*/

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