简单瞎搞题

显然可以dp。

dp[i][j] 为前i个数字能否构成j。

怎么状态转移呢？每次第i个数有一个对应区间，我们直接尝试加入区间的每一个数字，和前i-1个数能构成的数字去匹配。

我们就可以发现这样复杂度是：1e6 * 100 * 100为1e10，不过我们只需要知道能否构成，所以可以状态压缩，然后用bitset即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=110;
bitset<1000010> dp[N]; int n,l,r;
signed main(){
    cin>>n; dp[0][0]=1;
    for(int i=1;i<=n;i++){
        cin>>l>>r;    for(int j=l;j<=r;j++) dp[i]|=(dp[i-1]<<(j*j));
    }
    cout<<dp[n].count();
    return 0;
}