oj.uz

Submission #438679

# Submission time Handle Problem Language Result Execution time Memory
438679 2021-06-28T12:44:44 Z peijar Skyscraper (JOI16_skyscraper) C++17
20 / 100
 2000 ms 316924 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 0;
    if (!fL and !fR)
      return 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];
  if (lenPerm == 1) {
    cout << 1 << endl;
    return 0;
  }
  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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 190 ms 316900 KB Output is correct
3 Correct 160 ms 316888 KB Output is correct
4 Correct 176 ms 316748 KB Output is correct
5 Correct 182 ms 316840 KB Output is correct
6 Correct 158 ms 316780 KB Output is correct
7 Correct 158 ms 316764 KB Output is correct
8 Correct 152 ms 316784 KB Output is correct
9 Correct 162 ms 316740 KB Output is correct
10 Correct 157 ms 316924 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 316740 KB Output is correct
2 Correct 159 ms 316828 KB Output is correct
3 Correct 161 ms 316840 KB Output is correct
4 Correct 168 ms 316764 KB Output is correct
5 Correct 160 ms 316816 KB Output is correct
6 Correct 167 ms 316764 KB Output is correct
7 Correct 185 ms 316860 KB Output is correct
8 Correct 169 ms 316740 KB Output is correct
9 Correct 156 ms 316752 KB Output is correct
10 Correct 156 ms 316828 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 190 ms 316900 KB Output is correct
3 Correct 160 ms 316888 KB Output is correct
4 Correct 176 ms 316748 KB Output is correct
5 Correct 182 ms 316840 KB Output is correct
6 Correct 158 ms 316780 KB Output is correct
7 Correct 158 ms 316764 KB Output is correct
8 Correct 152 ms 316784 KB Output is correct
9 Correct 162 ms 316740 KB Output is correct
10 Correct 157 ms 316924 KB Output is correct
11 Correct 168 ms 316740 KB Output is correct
12 Correct 159 ms 316828 KB Output is correct
13 Correct 161 ms 316840 KB Output is correct
14 Correct 168 ms 316764 KB Output is correct
15 Correct 160 ms 316816 KB Output is correct
16 Correct 167 ms 316764 KB Output is correct
17 Correct 185 ms 316860 KB Output is correct
18 Correct 169 ms 316740 KB Output is correct
19 Correct 156 ms 316752 KB Output is correct
20 Correct 156 ms 316828 KB Output is correct
21 Correct 259 ms 316816 KB Output is correct
22 Correct 1402 ms 316860 KB Output is correct
23 Execution timed out 2108 ms 316868 KB Time limit exceeded
24 Halted 0 ms 0 KB -