oj.uz

Submission #438677

# Submission time Handle Problem Language Result Execution time Memory
438677 2021-06-28T12:35:16 Z peijar Skyscraper (JOI16_skyscraper) C++17
15 / 100
 201 ms 316868 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MOD = 1e9 + 7;
int lenPerm, maxSum;

int dp[100][1001][101][2][2];
// dp[curPos][curSum][ccCenter][fL][fR];
int diffs[101];

int solve(int curPos, int curSum, int ccCenter, bool fL, bool fR) {
  if (curSum > maxSum)
    return 0;

  int &cur = dp[curPos][curSum][ccCenter][fL][fR];
  if (cur != -1)
    return cur;
  cur = 0;

  curSum += fL * diffs[curPos];
  curSum += fR * diffs[curPos];
  curSum += ccCenter * diffs[curPos] * 2;
  if (curSum > maxSum)
    return 0;

  if (curPos == lenPerm - 1) {
    if (ccCenter > 0)
      return cur = 0;
    if (!fL and !fR)
      return cur = 0;
    return cur = 1;
  }

  // Create new cc :
  cur += solve(curPos + 1, curSum, ccCenter + 1, fL, fR);
  // Create new cc on side :
  if (!fL)
    cur += solve(curPos + 1, curSum, ccCenter, true, fR);
  if (!fR)
    cur += solve(curPos + 1, curSum, ccCenter, fL, true);
  // merge center and side :
  if (fL and ccCenter)
    cur += ccCenter * solve(curPos + 1, curSum, ccCenter - 1, true, fR);
  if (fR and ccCenter)
    cur += ccCenter * solve(curPos + 1, curSum, ccCenter - 1, fL, true);
  // merge centers :
  if (ccCenter >= 2)
    cur += ccCenter * (ccCenter - 1) *
           solve(curPos + 1, curSum, ccCenter - 1, fL, fR);
  // add to center :
  cur += 2 * ccCenter * solve(curPos + 1, curSum, ccCenter, fL, fR);
  // add to side:
  if (fL)
    cur += solve(curPos + 1, curSum, ccCenter, fL, fR);
  if (fR)
    cur += solve(curPos + 1, curSum, ccCenter, fL, fR);
  // Add to center and merge with side :
  if (!fL)
    cur += ccCenter * solve(curPos + 1, curSum, ccCenter - 1, true, fR);
  if (!fR)
    cur += ccCenter * solve(curPos + 1, curSum, ccCenter - 1, fL, true);
  cur %= MOD;
  return cur;
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> lenPerm >> maxSum;
  for (int i = 0; i < lenPerm; ++i) {
    cin >> diffs[i];
  }
  sort(diffs, diffs + lenPerm);
  for (int i = lenPerm - 1; i > 0; --i)
    diffs[i] -= diffs[i - 1];
  for (int i = 0; i < 100; ++i)
    for (int j = 0; j <= 1000; ++j)
      for (int k = 0; k <= 100; ++k)
        for (int l = 0; l < 2; ++l)
          for (int m = 0; m < 2; ++m)
            dp[i][j][k][l][m] = -1;
  cout << solve(0, 0, 0, 0, 0) << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 316736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 316788 KB Output is correct
2 Correct 158 ms 316832 KB Output is correct
3 Correct 162 ms 316840 KB Output is correct
4 Correct 170 ms 316740 KB Output is correct
5 Correct 163 ms 316796 KB Output is correct
6 Correct 160 ms 316860 KB Output is correct
7 Correct 163 ms 316760 KB Output is correct
8 Correct 152 ms 316868 KB Output is correct
9 Correct 182 ms 316844 KB Output is correct
10 Correct 165 ms 316800 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 201 ms 316736 KB Output isn't correct
2 Halted 0 ms 0 KB -