oj.uz

Submission #297111

# Submission time Handle Problem Language Result Execution time Memory
297111 2020-09-11T09:02:20 Z arman_ferdous Skyscraper (JOI16_skyscraper) C++17
100 / 100
 477 ms 520992 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 303 ms 520696 KB Output is correct
3 Correct 291 ms 520696 KB Output is correct
4 Correct 289 ms 520696 KB Output is correct
5 Correct 291 ms 520952 KB Output is correct
6 Correct 283 ms 520696 KB Output is correct
7 Correct 286 ms 520696 KB Output is correct
8 Correct 289 ms 520844 KB Output is correct
9 Correct 284 ms 520820 KB Output is correct
10 Correct 296 ms 520696 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 520696 KB Output is correct
2 Correct 291 ms 520696 KB Output is correct
3 Correct 294 ms 520824 KB Output is correct
4 Correct 295 ms 520824 KB Output is correct
5 Correct 295 ms 520696 KB Output is correct
6 Correct 288 ms 520696 KB Output is correct
7 Correct 287 ms 520732 KB Output is correct
8 Correct 288 ms 520728 KB Output is correct
9 Correct 288 ms 520868 KB Output is correct
10 Correct 285 ms 520824 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 303 ms 520696 KB Output is correct
3 Correct 291 ms 520696 KB Output is correct
4 Correct 289 ms 520696 KB Output is correct
5 Correct 291 ms 520952 KB Output is correct
6 Correct 283 ms 520696 KB Output is correct
7 Correct 286 ms 520696 KB Output is correct
8 Correct 289 ms 520844 KB Output is correct
9 Correct 284 ms 520820 KB Output is correct
10 Correct 296 ms 520696 KB Output is correct
11 Correct 299 ms 520696 KB Output is correct
12 Correct 291 ms 520696 KB Output is correct
13 Correct 294 ms 520824 KB Output is correct
14 Correct 295 ms 520824 KB Output is correct
15 Correct 295 ms 520696 KB Output is correct
16 Correct 288 ms 520696 KB Output is correct
17 Correct 287 ms 520732 KB Output is correct
18 Correct 288 ms 520728 KB Output is correct
19 Correct 288 ms 520868 KB Output is correct
20 Correct 285 ms 520824 KB Output is correct
21 Correct 292 ms 520700 KB Output is correct
22 Correct 477 ms 520696 KB Output is correct
23 Correct 334 ms 520700 KB Output is correct
24 Correct 360 ms 520696 KB Output is correct
25 Correct 350 ms 520824 KB Output is correct
26 Correct 336 ms 520992 KB Output is correct
27 Correct 323 ms 520708 KB Output is correct
28 Correct 339 ms 520744 KB Output is correct
29 Correct 396 ms 520824 KB Output is correct
30 Correct 357 ms 520796 KB Output is correct