Submission #44476100

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define de(x) cout<<#x<<"="<<x<<endl

using ll = long long;
using d = long double;

ll n,m,id[44],msk[44];
d a[44],b[44];
int x[100005],y[100005];
vector<int> pos,neg;
bool f[100005];
d dff[44],dfp[44],dfn[44];
d dp[44][1<<20];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cout<<fixed<<setprecision(10);
	cin>>n>>m;
	for (int i=0; i<n; i++){
		cin>>a[i]>>b[i];
	}
	for (int i=0; i<m; i++){
		cin>>x[i]>>y[i];
		x[i]--;
		y[i]--;
		if (x[i]==y[i] && a[x[i]]<b[x[i]]){
			swap(a[x[i]],b[x[i]]);
		}
	}
	d ans=0.;
	for (int i=0; i<n; i++){
		ans+=a[i];
		d df=(a[i]+b[i])/2.-a[i];
//		cout<<df<<endl;
		if (df>=0){
			id[i]=pos.size();
			dfp[id[i]]=df;
			pos.push_back(df);
			f[i]=0;
		}
		else{
			id[i]=neg.size();
			dfn[id[i]]=df;
			neg.push_back(df);
			f[i]=1;
		}
		dff[i]=df;
	}
//	cout<<ans<<endl;
	for (int i=0; i<m; i++){
		if (f[x[i]]!=f[y[i]]){
			if (f[x[i]]==0){
				swap(x[i],y[i]);
			}
			msk[id[x[i]]]|=1ll<<id[y[i]];
//			cout<<id[x[i]]<<": "<<msk[id[x[i]]]<<endl;
		}
		else{
			if (f[x[i]]==0){
				ans+=dff[x[i]]+dff[y[i]];
				dff[x[i]]=dff[y[i]]=0;
				dfp[id[x[i]]]=dfp[id[y[i]]]=0;
				pos[id[x[i]]]=pos[id[y[i]]]=0;
			}
		}
	}
	int ps=pos.size(),ns=neg.size();
//	cout<<ps<<","<<ns<<endl;
//	cout<<ans<<endl;
	if (ps>=ns){
		d res=0.;
		for (int i=0; i<(1<<ns); i++){
			d cur=0.;
			ll mk=0;
			for (int j=0; j<ns; j++){
				if ((i>>j)&1){
					cur+=dfn[j];
					mk|=msk[j];
				}
			}
			for (int j=0; j<ps; j++){
				if ((mk>>j)&1){
					cur+=dfp[j];
				}
			}
//			cout<<i<<": "<<cur<<endl;
			res=max(res,cur);
		}
		cout<<ans+res<<endl;
	}
	else{
		for (int i=0; i<=ns; i++){
			for (int j=0; j<(1<<ps); j++){
				dp[i][j]=-1000000000.;
			}
		}
		dp[0][0]=0.;
		for (int i=0; i<ns; i++){
			for (int j=0; j<(1<<ps); j++){
				dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
//				cout<<i+1<<","<<(j)<<": "<< dp[i+1][j]<<endl;
				dp[i+1][j|msk[i]]=max(dp[i+1][j|msk[i]],dp[i][j]+dfn[i]);
//				cout<<i+1<<","<<(j|msk[i])<<": "<< dp[i+1][j|msk[i]]<<endl;
			} 
		}
		d res=0.;
		for (int i=0; i<(1<<ps); i++){
			d cur=dp[ns][i];
			for (int j=0; j<ps; j++){
				if ((i>>j)&1){
					cur+=dfp[j];
				}
			}
//			cout<<i<<": "<<cur<<endl;
			res=max(res,cur);
		}
		cout<<ans+res<<endl;
	}
	return 0;
}

// don't waste time!!!

Submission Info

Judge Result