QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#312525 | #8137. 'Ello, and What Are You After, Then? | Kevin5307 | WA | 0ms | 3616kb | C++23 | 2.1kb | 2024-01-23 22:52:40 | 2024-01-23 22:52:40 |
Judging History
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<50;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<30;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: 0
Wrong Answer
time: 0ms
memory: 3616kb
input:
0 1 6 2 1 1 1 1 2 1 10 1 1 10 10
output:
6.99991360306739807129
result:
wrong answer 1st numbers differ - expected: '7.0000000', found: '6.9999136', error = '0.0000123'