QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#312521#8137. 'Ello, and What Are You After, Then?Kevin5307TL 1ms3896kbC++232.1kb2024-01-23 22:49:232024-01-23 22:49:24

Judging History

你现在查看的是最新测评结果

  • [2024-01-23 22:49:24]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3896kb
  • [2024-01-23 22:49:23]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
int b,c,s,n;
vector<array<int,3>> skill[1010];
int gen(int ind,double val,double cost)
{
	vector<array<double,3>> vec;
	for(auto arr:skill[ind])
	{
		double cost1=1.0*(arr[2]-val)*arr[1]+c*cost;
		double cost2=-s*cost;
		if(cost1>cost2)
			vec.pb(array<double,3>{cost1*arr[0],(1.0*(arr[2]-val)*arr[1])*arr[0],c*arr[0]});
		else
			vec.pb(array<double,3>{cost2*arr[0],0,-s*arr[0]});
	}
	rsrt(vec);
	int cnt=0;
	while(sz(vec)&&cnt<b&&vec.back()[0]<0)
	{
		cnt++;
		vec.pop_back();
	}
	double A=0,B=0;
	for(auto arr:vec)
	{
		A+=arr[1];
		B+=arr[2];
	}
	double sum=0;
	for(auto arr:vec)
		sum+=arr[0];
	if(sum<0) return 0;
	if(A>0&&B>0)
		return 1;
	if(A>0) return 2;
	return 4;
}
bool check(double val)
{
	double l=0,r=1e9;
	for(int i=0;i<100;i++)
	{
		double mid=(l+r)/2;
		int msk=0;
		for(int j=1;j<=n;j++)
			msk|=gen(j,val,mid);
		if(msk&1)
			return true;
		if(msk&2)
			if(msk&4)
				return true;
		if(!msk)
			return false;
		if(msk&2)
			l=mid;
		else
			r=mid;
	}
	return true;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>b>>c>>s>>n;
	for(int i=1;i<=n;i++)
	{
		int m;
		cin>>m;
		while(m--)
		{
			int f,t,e;
			cin>>f>>t>>e;
			skill[i].pb(array<int,3>{f,t,e});
		}
	}
	double l=0,r=1e5;
	for(int i=0;i<50;i++)
	{
		double mid=(l+r)/2;
		if(check(mid))
			l=mid;
		else
			r=mid;
	}
	printf("%.20lf\n",l);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3740kb

input:

0 1 6
2
1
1 1 1
2
1 10 1
1 10 10

output:

6.99999999991263166521

result:

ok found '7.0000000', expected '7.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3896kb

input:

2 1 2
1
4
10 2 1
10 1 1
1 10 1
1 1 10

output:

5.90909090902869138517

result:

ok found '5.9090909', expected '5.9090909', error '0.0000000'

Test #3:

score: -100
Time Limit Exceeded

input:

14 1000 1000
1000
30
113 80 1188
92 145 1074
130 56 1296
139 102 1142
60 76 1317
128 126 1208
73 120 1155
91 89 1197
115 64 979
80 118 592
110 97 556
83 105 578
94 51 848
98 134 757
107 138 1038
105 143 892
92 72 893
88 103 961
87 148 879
105 84 823
85 134 607
100 82 1084
199 58 801
138 85 743
214 1...

output:


result: