比赛 |
20160419x |
评测结果 |
AAAAAAAAAA |
题目名称 |
贿赂 |
最终得分 |
100 |
用户昵称 |
Satoshi |
运行时间 |
0.328 s |
代码语言 |
C++ |
内存使用 |
0.28 MiB |
提交时间 |
2016-04-19 16:03:36 |
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#define N 11
using namespace std;
typedef double ld;
ifstream in("bribe.in");
ofstream out("bribe.out");
int n,K;
ld A;
ld a[N]={0},b[N]={0},add[N]={0},win[N]={0},fail[N]={0};
bool l[N]={0};
int top=0;
ld ans=0;
void print(ld x,int y){out<<setprecision(y)<<std::fixed<<x<<endl;}
ld update()
{
int i,tolo=0;
ld sum=1;
ld solo=0;
for(i=1;i<=n;i++)
{
if(l[i])
{
sum*=win[i];
tolo++;//总共有多少人投了支持票
}
else
{
sum*=fail[i];
solo+=a[i];
}
}
if(tolo<=n/2)sum*=(A/(A+solo));//干掉那些人
memset(l,0,sizeof(l));
return sum;
}
void fuck()
{
int i,temp,cnt=0;
ld sum=0;
for(i=1;i<=n;i++)
{
win[i]=b[i]+add[i];
if(win[i]>10)win[i]=10;
win[i]/=10.0;
fail[i]=1-win[i];
//out<<win[i]<<' '<<fail[i]<<' '<<endl;
}
for(i=0;i<(1<<n);i++)
{
temp=i;
cnt=0;
while(temp)
{
l[++cnt]=temp%2;
temp=temp>>1;
}
sum+=update();
}
if(sum>ans)ans=sum;
}
void DFS(int tot,int pos)//糖果已经给了tot个人,位置指针指向pos
{
if(tot>K)return ;
if(pos==n+1)
{
if(tot==K)fuck();
return ;
}
else
{
for(int i=0;i<=K-tot;i++)
{
if(b[pos]+i>10.0)return ;
add[pos]=i;
DFS(i+tot,pos+1);
add[pos]=0;
}
}
}
void read()
{
int i;
in>>n>>K>>A;
for(i=1;i<=n;i++)
{
in>>a[i]>>b[i];
b[i]/=10.0;
}
}
void work()
{
DFS(0,1);
}
int main()
{
//int start,end;
//start=clock();
read();
work();
print(ans,6);
//end=clock();
//out<<end-start<<endl;
return 0;
}