Submission #297111

#	Time	Username	Problem	Language	Result	Execution time	Memory
297111		arman_ferdous	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	477 ms	520992 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define dbg(x) cerr << #x << " is " << x << "\n";

using ll = long long;
using ii = pair<ll,ll>;

const int N = 105;
const int L = 2010;
const int MOD = 1e9+7;

int n, lim, a[N];

ll dp[3][N][N][L];

ll DP(int lr, int i, int comp, int curans) {
  if(curans > lim) return 0;
  if(i > n) return lr == 2 && comp == 1;

  ll &ret = dp[lr][i][comp][curans];
  if(ret != -1) return ret;
  ret = 0;

  if(lr < 2) { // put a[i] at one of the free endpoints
    if(i == n) { // special situation where we have to merge with the other end
      ret += DP(lr + 1, i + 1, comp, curans + (2 * comp - lr - 1) * (a[i + 1] - a[i]));
      ret %= MOD;
    }
    // we can choose to merge it too (there has to be another endpoint free component for that)
    else if(comp - lr > 0) {
      ret += (2 - lr) * (comp - lr) * DP(lr + 1, i + 1, comp, curans + (2 * comp - lr - 1) * (a[i + 1] - a[i]));
      ret %= MOD; 
    }
    // it can be a new component
    ret += (2 - lr) * DP(lr + 1, i + 1, comp + 1, curans + (2 * comp - lr + 1) * (a[i + 1] - a[i]));
    ret %= MOD;
  }

  // if(i <= n - 2) { // this number can create a new cc in middle
    ret += DP(lr, i + 1, comp + 1, curans + (2 * comp - lr + 2) * (a[i + 1] - a[i]));
    ret %= MOD;
  // }
  if(comp > 0) { // this number can merge with one component
    ret += (2 * comp - lr) * DP(lr, i + 1, comp, curans + (2 * comp - lr) * (a[i + 1] - a[i]));
    ret %= MOD;
  }
  if(comp >= 2) { // this number can merge two components together
    // but there are some caseworks with lr
    if(lr == 0) { 
      // P(comp, 2) ways
      ret += (1LL * comp * (comp - 1)) * DP(lr, i + 1, comp - 1, curans + (2 * comp - lr - 2) * (a[i + 1] - a[i]));
      ret %= MOD;
    }
    else if(lr == 1) {
      // P(comp - 1, 2) + comp - 1 = (comp - 1)^2
      ret += (1LL * (comp - 1) * (comp - 1)) * DP(lr, i + 1, comp - 1, curans + (2 * comp - lr - 2) * (a[i + 1] - a[i]));
      ret %= MOD;
    }
    else {
      // you cant add the leftmost and rightmost endpoints before everything in the middle is merged
      if(i == n) { // only time you can merge left-end with right-end
        ret += DP(lr, i + 1, comp - 1, curans + (2 * comp - lr - 2) * (a[i + 1] - a[i]));
        ret %= MOD;
      }
      else { // P(comp - 2, 2) + 2 * (comp - 2) = (comp - 1) * (comp - 2)
        ret += (1LL * (comp - 1) * (comp - 2)) * DP(lr, i + 1, comp - 1, curans + (2 * comp - lr - 2) * (a[i + 1] - a[i]));
        ret %= MOD;
      }
    }
  }
  return ret;
}

int main() {
  scanf("%d %d", &n, &lim);
  for(int i = 1; i <= n; i++) 
    scanf("%d", &a[i]);
  sort(a + 1, a + n + 1);
  a[n + 1] = a[n];

  // sneaky
  if(n == 1) {
    puts("1");
    return 0;
  }

  memset(dp, -1, sizeof dp);
  printf("%lld\n", DP(0, 1, 0, 0));
  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |   scanf("%d %d", &n, &lim);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
skyscraper.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~

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