#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,...

Unable to parse markup [type=CF_MATHJAX]

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}$$$.

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 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...