C++14(g++5.4) 解法, 执行用时: 773ms, 内存消耗: 1016K, 提交时间: 2019-05-18 15:38:55

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	bitset<1010000>a,b;
	b=1;
	while(n--)
	{	
		int l,r;
		cin>>l>>r;
		a.reset();
		for(int i=l;i<=r;i++)
			a|=b<<(i*i);
			
		b=a;
	}
	cout<<b.count()<<endl;
	return 0; 
}

C++(g++ 7.5.0) 解法, 执行用时: 513ms, 内存消耗: 12912K, 提交时间: 2023-07-03 01:48:00

#include <bits/stdc++.h>
using namespace std;
int t,n,m,l,r;
bitset<1000100>dp[110];
int 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()<<endl;
}

C++(clang++ 11.0.1) 解法, 执行用时: 476ms, 内存消耗: 13020K, 提交时间: 2023-07-29 10:35:51

#include<bits/stdc++.h>
using namespace std;
int n,l,r,i,j;
bitset<1000005>f[105]; 
int main(){
    cin>>n,f[0]=1;
    for(i=1;i<=n;i++){
        cin>>l>>r;
        for(j=l;j<=r;j++) f[i]|=f[i-1]<<j*j;
    }
    cout<<f[n].count();
}