QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#312521 | #8137. 'Ello, and What Are You After, Then? | Kevin5307 | TL | 1ms | 3896kb | C++23 | 2.1kb | 2024-01-23 22:49:23 | 2024-01-23 22:49:24 |
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<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...