#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n;
                cin >> n;

                vector<int> a(n);
                vector<int> b(n);

                for (int i = 0; i < n; i++) cin >> a[i];
                for (int i = 0; i < n; i++) cin >> b[i];

                vector<int> ord(n);
                iota(ord.begin(), ord.end(), 0);
                sort(ord.begin(), ord.end(), [&](int x, int y) {
                        if (b[x] == b[y]) return a[x] > a[y];
                        return b[x] == 1;
                });

                int ans = a[0] * b[0];
                int suma = 0, sumb = 0;

                for (int i = 0; i < n; i++) {
                        suma += a[ord[i]];
                        sumb += b[ord[i]];

                        ans = max(ans, suma * sumb);
                        ans = max(ans, a[i] * b[i]);
                }

                cout << ans << '\n';
        }

        return 0;
}

Consider greedy algorithm.

When all $$$b_i(1 \leq i \leq n)=-1$$$,obviously,the answer is $$$-min(a_i)$$$.

Otherwise,we choose all tuples which's $$$b_i=1$$$ firstly.Then choose tuples in descending order of $$$a_i$$$ value which's $$$b_i=-1$$$.The answer is the maximum in this process.

Submitting this code directly will get ILE, please delete cerr and submit.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n;
                cin >> n;

                vector<int> ca(2 * n);
                vector<int> cb(2 * n);

                for (int i = 0; i < n; i++) {
                        int x;
                        cin >> x;
                        --x;

                        ca[x] += 1;
                }

                for (int i = 0; i < n; i++) {
                        int x;
                        cin >> x;
                        --x;

                        cb[x] += 1;
                }

                bool ok = 1;

                for (int i = 0; i < 2 * n; i++) {
                        if (ca[i] + cb[i] > n) {
                                ok = 0;
                        }
                }

                cout << (ok ? "YES" : "NO") << '\n';
        }
        
        return 0;
}

Note $$$k$$$ is the number with the highest sum of occurrences in $$$s$$$ and $$$t$$$.The answer is "YES" iff $$$occurrences(k) \leq n$$$.

If $$$occurrences(k) > n$$$,it means the total of numbers that are not $$$k$$$ is less than $$$n$$$.Obviously the answer is "NO".

Otherwise,we can use Mathematical induction to prove that there is a solution:

• 1.For two empty sets $$$s$$$,$$$t$$$,$$$occurrences(k) \leq n$$$ holds;

• 2.Assume for two empty sets $$$s$$$,$$$t$$$ if size $$$n$$$,$$$occurrences(k) \leq n$$$ holds.We do remove a $$$k$$$ from one set and remove a number which is not $$$k$$$ from another set.After that,the size becomes $$$n-1$$$,and $$$occurrences(k) \leq n-1$$$ holds.

#include<bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
using namespace std;
#define fastio  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define pb push_back
#define PI acos(-1)
#define pii pair<int,int>
#define endl "\n"
#define all(a) a.begin(),a.end()
#define len(s) (int)s.size()
#define F first
#define S second
const int mod=1e9+7;
int dp[20001][101][101];
int a[101];
const int add=10000;
const int L=-10000;
const int R=10000;
int f(int sum,int l,int r)
{
	//count number of non-empty subsequence of subarray [l,r] 
	//with adding=sum
	if( !(sum>=L and sum<=R))
		return 0;
	
	if(l==r)
	{

		if(sum==a[l])
			return 1;
		return 0;
	}
	if(dp[sum+add][l][r]!=-1)
		return dp[sum+add][l][r];
	int ans1=f(sum,l,r-1);
	int ans2=f(sum,l+1,r);
	int rem=0;
	if(l+1<=r-1)
		rem=f(sum,l+1,r-1);
	int ans3=0;
	if(l+1<=r-1)
		ans3=f(sum-a[l]-a[r],l+1,r-1)+(sum==(a[l]+a[r]));
	else
		ans3=(sum==(a[l]+a[r]));
	
	return dp[sum+add][l][r]=(((ans1+ans2)%mod-rem+mod)%mod+ans3)%mod;
}
void solve()
{
	int n,x;
	cin>>n>>x;
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;i++)
		cin>>a[i];
	if(n<3)
	{
		cout<<0;
		return ;
	}
	else
	{
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++)
			a[i]-=x;
		int ans=0;
	
		for(int i=1;i<=n;i++)
		{
			for(int j=i+2;j<=n;j++)
			{
				ans+=f(0,i+1,j-1);
				ans%=mod;
			}
		}
		cout<<ans;
	}
}
signed main()
{
fastio
int TestCases=1;
//cin>>TestCases;
while(TestCases--)
{
solve();
cout<<endl;
}
}

Firstly,we substract all $$$a_i$$$ by $$$x$$$.Then the problem is equivent to count the number of subsequences which's sum is $$$0$$$.

Consider sort the array and do DP.Note $$$dp_{l,r,s}$$$ as the number of subsequences with $$$a_l$$$ as the head, $$$a_r$$$ as the tail, and $$$s$$$ as the sum.

For $$$dp_{l,r,0}(2\leq l \leq r \leq n-1)$$$,it's contribution is $$$dp_{l,r,0}*(l-1)*(n-r)$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int MOD = 1e9 + 7;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        vector<int> fac(2222222);

        fac[0] = 1;
        for (int i = 1; i <= 2000000; i++) {
                fac[i] = (fac[i - 1] * i) % MOD;
        }

        auto binpow = [&](int x, int y) {
                int res = 1;

                while (y > 0) {
                        if (y & 1) (res *= x) %= MOD;

                        (x *= x) %= MOD;
                        y >>= 1;
                }

                return res;
        };

        vector<int> inv(2222222);

        inv[2000000] = binpow(fac[2000000], MOD - 2);
        for (int i = 1999999; i >= 0; i--) {
                inv[i] = (inv[i + 1] * (i + 1)) % MOD;
        }

        auto comb = [&](int n, int r) {
                if (n < r) {
                        cout << "hi\n";
                        exit(0);
                }
                return fac[n] * inv[r] % MOD * inv[n - r] % MOD;
        };

        int t;
        cin >> t;

        while (t --> 0) {
                int n, m;
                cin >> n >> m;
                // general case: a1 + a2 + a3 + .. + an = m -> C(m - 1, n - 1)
                int ans = comb(m - 1, n - 1);

                if (n - 1 <= m - (m + 1) / 2) {
                        ans -= n * comb(m - (m + 1) / 2 - 1 + 1, n - 1 - 1 + 1);
                }

                ans %= MOD;
                ans += MOD;
                ans %= MOD;

                cout << ans << '\n';
        }
        
        return 0;
}

As we all know,the sum of the two sides of a triangle is greater than the third side.Similarly,we can infer condition $$$3$$$ is equviant to $$$max(a_i)< \lceil m/2 \rceil$$$.

What's the number of arrays satisfying the following condition?

• 1.All $$$a_i$$$ are positive integers;

• 2.$$$\Sigma a_i=m$$$.

The answer is $$$C^{m-1}_{n-1}$$$.It's a classic problem.

$$$C^i_j+C^{i-1}_j+...+C^j_j=C^{i+1}_{j+1}$$$.

We find it's easier to calculate bad arrays.When $$$max(a_i)=\lceil m/2 \rceil,\lceil m/2 \rceil+1,...$$$,$$$a$$$ is a bad array.

The total of bad array is $$$n*(C^{m-\lceil m/2 \rceil}_{n-2}+C^{m- \lceil m/2 \rceil-1}_{n-2}+...)=n*C^{\lfloor m/2 \rfloor}_{n-1}$$$.

The final answer is $$$C^{m-1}_{n-1}-n*C^{\lfloor m/2 \rfloor}_{n-1}$$$

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int INFF = 1e18;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n, m, s;
                cin >> n >> m >> s;

                set<pair<int, int>> st;
                st.insert({s, 0});

                for (int i = 0; i < m; i++) {
                        int l, r;
                        cin >> l >> r;

                        vector<pair<int, int>> del;
                        int mnl = INFF, mnr = INFF;
                        for (auto it = st.lower_bound({l, 0}); it != st.end(); it++) {
                                if (it->fi > r) break;

                                if (l - 1 >= 1) {
                                        mnl = min(mnl, it->se + it->fi - l + 1);
                                }

                                if (r + 1 <= n) {
                                        mnr = min(mnr, it->se + r + 1 - it->fi);
                                }

                                del.push_back(*it);
                        }
                        
                        for (auto p : del) st.erase(p);

                        auto it = st.lower_bound({l - 1, 0});
                        if (it != st.end() && it->fi == l - 1) {
                                mnl = min(mnl, it->se);
                                st.erase(it);
                        }

                        auto it2 = st.lower_bound({r + 1, 0});
                        if (it2 != st.end() && it2->fi == r + 1) {
                                mnr = min(mnr, it2->se);
                                st.erase(it2);
                        }

                        if (l - 1 >= 1) {
                                st.insert({l - 1, mnl});
                        }

                        if (r + 1 <= n) {
                                st.insert({r + 1, mnr});
                        }
                }

                int ans = INFF;

                for (auto [pos, cost] : st) {
                        ans = min(ans, cost);
                }

                cout << ans << '\n';
        }
        
        return 0;
}

Coming soon...

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int MOD = 1e9 + 7;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        vector<bool> ok(22222, 0);

        auto conv = [&](int x) {
                int res = 0;

                while (x > 0) {
                        int y = x % 10;

                        res += y * y;
                        x /= 10;
                }

                return res;
        };

        for (int i = 1; i <= 16200; i++) {
                int x = i;

                set<int> vis;
                
                while (!vis.count(x)) {
                        vis.insert(x);

                        int y = conv(x);
                        if (x == y) {
                                ok[i] = 1;
                        }
                        x = y;
                }
        }
        
        vector<vector<int>> dp(222, vector<int>(22222)); // digit - sum
        dp[0][0] = 1;

        for (int i = 1; i <= 200; i++) {
                for (int j = 0; j < 20000; j++) {
                        for (int k = 0; k <= 9; k++) {
                                dp[i][j + k * k] += dp[i - 1][j];
                                dp[i][j + k * k] %= MOD;
                        }
                }
        }

        int t;
        cin >> t;

        while (t --> 0) {
                string l, r;
                cin >> l >> r;

                auto calc = [&](string s, bool on) {
                        int res = 0;
                        int n = (int)s.length();
                        int cur = 0;

                        for (int i = 0; i < n; i++) {
                                for (int j = 0; j < s[i] - '0'; j++) {
                                        for (int k = cur + j * j; k <= 16200; k++) {
                                                res += ok[k] * dp[n - i - 1][k - (cur + j * j)];
                                                res %= MOD;
                                        }
                                }
                                cur += (s[i] - '0') * (s[i] - '0');
                        }

                        if (ok[cur] && on) res += 1;

                        return res;
                };
                
                int ans = calc(r, 1) - calc(l, 0);
                ans %= MOD;
                ans += MOD;
                ans %= MOD;

                cout << ans << '\n';
        }
        return 0;
}

Notice that the biggest number we can obtain after exactly one operation is $$$81 \cdot 200 = 16200$$$.

We can solve the problem with digit DP (or DFS with memorization). Let $$$AN$$$ be the number of happy numbers less than or equal to $$$N$$$. Our answer would then be $$$A{ri} - A{l_i - 1}$$$.

Now we are interested in calculating $$$AN$$$ for some integer $$$N$$$. We do a DFS from the leftmost digit to the rightmost digit. Let $$$f{i, j}$$$ denote the number of happy numbers, less than or equal to $$$N$$$, with the sum of the first $$$i$$$ digits squared equal to $$$j$$$. We can do a DFS from left to right, taking note of whether the current digit sequence is exactly the same as $$$N$$$'s first digits; if not so, we can memorize the answer with $$$f_{i, j}$$$ (to avoid repeated calculations).

It is not hard to see that we are expected to reach every state once, and we can re-use $$$f$$$ over all test cases. Thus, the time complexity is $$$O(DS)$$$, where $$$D \leq 201$$$ is the number of digits and $$$S \leq 16200$$$ is the digit-squared sum.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")

#define int long long
const int bk=500;
namespace sumadd {
   int tag[bk],pb[bk],pre[bk][bk];
   void addib(int l,int r,int id,int v) {
      for(int i=0,x=0;i<=bk-1;++i){if(l<=i&&i<=r)x+=v;x+=tag[id];pre[id][i]+=x;}
      tag[id]=0;
   }
   void add(int l,int r,int v) {
      if(l/bk==r/bk) {
         addib(l%bk,r%bk,l/bk,v);
         for(int i=0;i<=bk-1;++i) pb[i]=(i==0?0:pb[i-1])+pre[i][bk-1]+tag[i]*bk;
         return;
      }
      if(l%bk!=0) {addib(l%bk,bk-1,l/bk,v);l+=bk-l%bk;}
      if(r%bk!=bk-1) {addib(0,r%bk,r/bk,v);r-=r%bk+1;}
      while(l<=r) {tag[l/bk]+=v;l+=bk;}
      for(int i=0;i<=bk-1;++i) pb[i]=(i==0?0:pb[i-1])+pre[i][bk-1]+tag[i]*bk;
   }
   int sum(int l,int r) {
      if(l/bk==r/bk) {
         return (r-l+1)*tag[l/bk]+pre[l/bk][r%bk]-(l%bk==0?0:pre[l/bk][l%bk-1]);
      }
      int sum=0;
      if(l%bk!=0) {sum+=tag[l/bk]*(bk-l%bk)+pre[l/bk][bk-1]-(l%bk==0?0:pre[l/bk][l%bk-1]);l+=bk-l%bk;}
      if(r%bk!=bk-1) {sum+=tag[r/bk]*(r%bk+1)+pre[r/bk][r%bk];r-=r%bk+1;}
      sum+=pb[r/bk]-(l==0?0:pb[l/bk-1]);
      return sum;
   }
   void cln() {
      for(int i=0;i<bk;++i) {
         tag[i]=pb[i]=0;
         for(int j=0;j<bk;++j)
            pre[i][j]=0;
      }
   }
}
pair<int,int> ivl[bk][bk];
array<int,4> qry[bk*bk];
int cnt[bk*bk],ans[bk*bk],flag[bk*bk];
vector<int> lp={0};
void Delta() {
   int n,m,q;
   cin >> n >> m >> q;
   for(int i=1,l,r;i<=m;++i) {
      cin >> l >> r;
      ivl[i/bk][i%bk]={l,r};
      lp.push_back(lp.end()[-1]+r-l+1);
   }
   cerr << endl;
   lp.push_back(2147483647);
   for(int i=1,o,l,r,v;i<=q;++i) {
      cin >> o >> l >> r;
      if(o==1) {cin >> v;qry[i]={1,l,r,v};sumadd::add(l,r,v);}
      else {
         auto il=lower_bound(lp.begin(),lp.end(),l-1),ir=prev(lower_bound(lp.begin(),lp.end(),r+1));
         qry[i]={2,il-lp.begin()+1,ir-lp.begin(),0};
         if(qry[i][1]==qry[i][2]+2) {
            int p=qry[i][2]+1;
            auto t=ivl[p/bk][p%bk];
            l-=*prev(il);r-=*prev(il);
            ans[i]=sumadd::sum(t.first+l-1,t.first+r-1);
            flag[i]=true;
            continue;
         }
         if(qry[i][1]==qry[i][2]+1) {
            ans[i]=sumadd::sum(ivl[qry[i][2]/bk][qry[i][2]%bk].first+l-*prev(il)-1,ivl[qry[i][2]/bk][qry[i][2]%bk].second);
            ans[i]+=sumadd::sum(ivl[qry[i][1]/bk][qry[i][1]%bk].first,ivl[qry[i][1]/bk][qry[i][1]%bk].first+r-*ir-1);
            flag[i]=true;
            continue;
         }
         if(il!=lp.begin()) {
            int p=qry[i][1]-1;l=*il-l+1;
            auto t=ivl[p/bk][p%bk];
            ans[i]+=sumadd::sum(t.second+1-l,t.second);
         }
         if(next(ir)!=lp.end()) {
            r-=*ir;
            int p=qry[i][2]+1;
            auto t=ivl[p/bk][p%bk];
            ans[i]+=sumadd::sum(t.first,t.first+r-1);
         }
         if(flag[i]) ans[i]=-ans[i];
      }
   }
   sumadd::cln();
   for(int k=0;k<bk;++k) {
      int sum=0;
      for(int i=0;i<bk;++i) {
         auto t=ivl[k][i];
         if(t==pair<int,int>{0,0}) continue;
         cnt[t.first]++;
         cnt[t.second+1]--;
      }
      for(int j=1;j<=2;++j)
         for(int i=1;i<=n;++i)
            cnt[i]+=cnt[i-1];
      for(int i=1;i<=q;++i)
         if(qry[i][0]==1) {
            sum+=qry[i][3]*(cnt[qry[i][2]]-(qry[i][1]==0?0:cnt[qry[i][1]-1]));
         }
         else
            if(!flag[i]&&qry[i][1]<=k*bk&&k*bk+bk-1<=qry[i][2]) ans[i]+=sum;
      for(int i=1;i<=n;++i) cnt[i]=0;
   }
   for(int i=1;i<=q;++i)
      if(qry[i][0]==1)
         sumadd::add(qry[i][1],qry[i][2],qry[i][3]);
      else {
         if(flag[i]) continue;
         int l=qry[i][1],r=qry[i][2];
         if(l>r) continue;
         if(l/bk==r/bk&&l%bk!=0&&r%bk!=bk-1) {
            for(int j=l;j<=r;++j) {
               auto t=ivl[j/bk][j%bk];
               ans[i]+=sumadd::sum(t.first,t.second);
            }
            continue;
         }
         while(l%bk!=0)    {auto t=ivl[l/bk][l%bk];ans[i]+=sumadd::sum(t.first,t.second);l++;}
         while(r%bk!=bk-1) {auto t=ivl[r/bk][r%bk];ans[i]+=sumadd::sum(t.first,t.second);r--;}
      }
   for(int i=1;i<=q;++i)
      if(qry[i][0]==2)
         cout << ans[i] << ' ';
   cout << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   Delta();
}

Coming soon...