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
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;
| ^~~~
