Submission #438683

#	Time	Username	Problem	Language	Result	Execution time	Memory
438683		peijar	Skyscraper (JOI16_skyscraper)	C++17	Compilation error	0 ms	0 KiB

skyscraper

for((i = 1; ; ++i)); do # if they are same then will loop forever
    echo $i
    ./gen $i > int
    ./A < int > out1
    ./B < int > out2
    diff -w out1 out2 || break
    # diff -w <(./A < int) <(./B < int) || break
done#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 :
  if (ccCenter)
    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;
}

void iterative() {
  for (int curPos = lenPerm - 1; curPos >= 0; --curPos)
    for (int _curSum = 0; _curSum <= maxSum; ++_curSum)
      for (int ccCenter = 0; ccCenter <= lenPerm; ++ccCenter)
        for (int fL = 0; fL < 2; ++fL)
          for (int fR = 0; fR < 2; ++fR) {
            int &cur = dp[curPos][_curSum][ccCenter][fL][fR];
            cur = 0;

            int curSum = _curSum;
            curSum += fL * diffs[curPos];
            curSum += fR * diffs[curPos];
            curSum += ccCenter * diffs[curPos] * 2;
            if (curSum > maxSum)
              continue;

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

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

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;
  }
  iterative();
  cout << dp[0][0][0][0][0] << 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;
}

Compilation message (stderr)

skyscraper.cpp:1:25: error: stray '#' in program
    1 | for((i = 1; ; ++i)); do # if they are same then will loop forever
      |                         ^
skyscraper.cpp:7:7: error: invalid preprocessing directive #diff; did you mean #if?
    7 |     # diff -w <(./A < int) <(./B < int) || break
      |       ^~~~
      |       if
skyscraper.cpp:8:5: error: stray '#' in program
    8 | done#include <bits/stdc++.h>
      |     ^
skyscraper.cpp:1:1: error: expected unqualified-id before 'for'
    1 | for((i = 1; ; ++i)); do # if they are same then will loop forever
      | ^~~
skyscraper.cpp:1:15: error: expected unqualified-id before '++' token
    1 | for((i = 1; ; ++i)); do # if they are same then will loop forever
      |               ^~
skyscraper.cpp:1:22: error: expected unqualified-id before 'do'
    1 | for((i = 1; ; ++i)); do # if they are same then will loop forever
      |                      ^~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:133:3: error: 'ios_base' has not been declared
  133 |   ios_base::sync_with_stdio(false);
      |   ^~~~~~~~
skyscraper.cpp:134:3: error: 'cin' was not declared in this scope
  134 |   cin.tie(0);
      |   ^~~
skyscraper.cpp:140:3: error: 'sort' was not declared in this scope; did you mean 'short'?
  140 |   sort(diffs, diffs + lenPerm);
      |   ^~~~
      |   short
skyscraper.cpp:144:5: error: 'cout' was not declared in this scope
  144 |     cout << 1 << endl;
      |     ^~~~
skyscraper.cpp:144:18: error: 'endl' was not declared in this scope
  144 |     cout << 1 << endl;
      |                  ^~~~
skyscraper.cpp:148:3: error: 'cout' was not declared in this scope
  148 |   cout << dp[0][0][0][0][0] << endl;
      |   ^~~~
skyscraper.cpp:148:32: error: 'endl' was not declared in this scope
  148 |   cout << dp[0][0][0][0][0] << endl;
      |                                ^~~~