简单瞎搞题 - 牛客

PS：怎么没想到用bitset优化，orz。

#include<bits/stdc++.h>
#include<bitset>
#define ll long long
#define P pair<int, int>
#define PP pair<int,pair<int, int>>
#define pb push_back
#define pp pop_back
#define lson root << 1
#define INF (int)2e9 + 7
#define rson root << 1 | 1
#define LINF (unsigned long long int)1e18
#define mem(arry, in) memset(arry, in, sizeof(arry))
using namespace std;int n;
bitset<1000005> dp[2];int main()
{cin >> n;dp[0][0] = 1;int now = 0, l, r;for(int i = 1; i <= n; i++) {cin >> l >> r;for(int j = l; j <= r; j++) dp[now ^ 1] |= dp[now] << (j * j);dp[now].reset();now ^= 1;}cout << dp[now].count() << endl;return 0;
}