提出 #33776745

---

ソースコード 拡げる

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
const int U=2e7;
vector<bool>prime(U+1,true);

ll solve(vector<pair<int,int>>odd, vector<pair<int,int>>even){
  int o=odd.size(),e=even.size();
  mf_graph<ll>g(o+e+2);//[0,o),[o,o+e),S=o+e,T=o+e+1
  int S=o+e,T=o+e+1;
  for(int i=0;i<o;i++)for(int j=0;j<e;j++){
    if(prime[odd[i].first+even[j].first])g.add_edge(i,o+j,1e9);
  }
  for(int i=0;i<o;i++)g.add_edge(S,i,odd[i].second);
  for(int i=0;i<e;i++)g.add_edge(o+i,T,even[i].second);
  return g.flow(S,T);
}

int main(){
  for(int i=2;i<=U;i++)if(prime[i])for(int j=i+i;j<=U;j+=i)prime[j]=false;
  
  vector<pair<int,int>>odd,even;
  int one_cnt=0;
  int n;
  cin >> n;
  for(int i=0;i<n;i++){
    int a,b;
    cin >> a >> b;
    if(a==1)one_cnt=b;
    else if(a%2)odd.push_back({a,b});
    else even.push_back({a,b});
  }
  ll ret1=solve(odd,even);
  odd.push_back({1,one_cnt});
  ll ret2=solve(odd,even);
  cout << ret2 + (one_cnt-(ret2-ret1))/2 << endl;
}

提出情報

ジャッジ結果