可以看一下您的代码吗?
by yukimianyan @ 2021-09-21 01:47:38
那只有可能是越界了吧
by Isshiki·Iroha @ 2021-09-21 08:25:05
@[yukimianyan](/user/509229) 你好,题目是
P4799 [CEOI2015 Day2]世界冰球锦标赛
```cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;
int n, cnta = 0, cntb = 0;
long long suma[5000000] = {0}, sumb[5000000] = {0}, price[5000000] = {0}, m, ans = 0;
void dfs(long long s[], int pos, int end, long long summ, int &cnt)
{
if (summ > m)
return;
if (pos > end)
{
s[cnt++] = summ;
return;
}
dfs(s, pos + 1, end, summ + price[pos], cnt);
dfs(s, pos + 1, end, summ, cnt);
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
scanf("%lld", &price[i]);
}
int mid = n >> 1;
dfs(suma, 0, mid - 1, 0, cnta);
dfs(sumb, mid, n - 1, 0, cntb);
sort(suma, suma + cnta);
for (int i = 0; i < cntb; i++)
{
ans += upper_bound(suma, suma + cnta, m - sumb[i]) - suma;
}
cout << ans << endl;
}
```
其中suma,sumb数组在题中数据是0-40,但是设为0-5000都有出现tle和wr,只有改更大才不会出现,不知道为什么
by debug_noob @ 2021-09-22 00:13:05
@[debug_noob](/user/430773) 您好,刚刚看了您的代码,我发现了一个问题。
如果 $n=40,m=10^{18},price_i=1$,那么 $cnt$ 的数值将会达到最大,为 $2^{\frac{n}{2}}$,这个数值约 $10^6$ 左右。我猜测正是这个问题,才导致程序 WA/TLE。
by yukimianyan @ 2021-09-22 00:30:12
@[yukimianyan](/user/509229) 多谢,懂了!
by debug_noob @ 2021-09-22 00:38:52