先按照等级从小到大排序。

考虑先二分答案,把所有等级符合要求的三元组存下来,随机顺序贪心即可。

更具体地,开一个vector把所有符合要求的三元组存下来,贪心的时候,如果当前的和之前的和为质数,那就不选,否则选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
struct node{int x,y,z;}a[105];
int n,k,p[10000005],v[10000005],cnt;
mt19937 rd((unsigned long long)new char);
bool check(int mid){
vector<node>b,chz;
for(int i=1;i<=n&&a[i].z<=mid;++i)b.push_back(a[i]);
int ans=0;
for(int i=1;i<=300;++i){
int sum=0;
for(int j=0;j<b.size();++j){
int flag=1;
for(auto[x,y,z]:chz)
if(!v[b[j].y+y]){flag=0;break;}
if(flag){chz.push_back(b[j]);sum+=b[j].x;}
}
ans=max(ans,sum);
chz.clear();
shuffle(b.begin(),b.end(),rd);
}
return ans>=k;
}
int main(){
for(int i=2;i<=10000000;++i){
if(!v[i]){
p[++cnt]=i;
for(int j=i*2;j<=10000000;j+=i)v[j]=1;
}
}
cin>>n>>k;
for(int i=1;i<=n;++i)cin>>a[i].x>>a[i].y>>a[i].z;
sort(a+1,a+n+1,[&](node x,node y){return x.z<y.z;});
int l=1,r=n+1;
while(l<r){
int mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
if(l>n)cout<<"-1\n";
else cout<<l<<'\n';
return 0;
}