求助CF 999 Div.2E
  • 板块灌水区
  • 楼主alpharchmage
  • 当前回复4
  • 已保存回复4
  • 发布时间2025/1/21 15:22
  • 上次更新2025/1/21 17:08:07
查看原帖
求助CF 999 Div.2E
411141
alpharchmage楼主2025/1/21 15:22

就是调不出来

#include<bits/stdc++.h>
#define int long long
#define inf (int)((1 << 30) - 1)
using namespace std;
int T = 0;
int n = 0 , m = 0 , k = 0;
array<int , 200100> arr;
array<int , 20> num , dp;
array<int , 1200> tag;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> T;
	while(T --)
	{
		cin >> n >> m >> k;
		int sum = 0;
		for(int i = 1;i <= n;++ i) cin >> arr[i] , sum += arr[i];
		for(int i = 1;i <= m;++ i) cin >> num[i];
		tag.fill(inf);
		for(int i = 0;i < (1 << m);++ i)
		{
			for(int k = 1;k <= m;++ k)
			{
				if(i & (1 << (k - 1)))
				{
					tag[i] &= num[k];
				}
			}
		}
		vector<int> tmp(n * m);
		for(int i = 1;i <= n;++ i)
		{
			dp.fill(inf);
			for(int k = 0;k < (1 << m);++ k)
			{
				int cnt = __builtin_popcount(k);
				dp[cnt] = min(dp[cnt] , arr[i] & tag[k]);
			}
			for(int k = 0;k < m;++ k)
			{
				tmp.push_back(dp[k] - dp[k + 1]);
			}
		}
		sort(tmp.begin() , tmp.end() , [&](int x , int y){return x > y;});
		cout << sum - accumulate(tmp.begin() , tmp.begin() + k , 0) << '\n';
	}
	cout << endl;
	return 0; 
}
2025/1/21 15:22
加载中...