QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#312527 | #8137. 'Ello, and What Are You After, Then? | Kevin5307 | TL | 1728ms | 5088kb | C++23 | 2.1kb | 2024-01-23 22:53:13 | 2024-01-23 22:53:14 |
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=1e-6,r=1e6;
for(int i=0;i<50;i++)
{
double mid=sqrt(l*r);
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: 3940kb
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: 3692kb
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: 0
Accepted
time: 1096ms
memory: 4260kb
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:
1453.36457904567942023277
result:
ok found '1453.3645790', expected '1453.3645790', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1006ms
memory: 5088kb
input:
8720 713 168 1 30000 1 186 5272 2 53 5132 2 124 5529 2 186 5052 2 82 5342 2 178 5027 1 74 5271 2 154 5506 1 185 5225 2 60 5068 2 85 5179 1 193 5231 1 94 5469 2 168 5317 2 142 5153 2 44 5083 2 71 5318 2 53 5325 1 68 5051 2 53 5424 2 150 5125 2 122 5371 2 126 5171 2 39 5315 2 57 5193 1 130 5203 2 179 ...
output:
5276.12718345542634779122
result:
ok found '5276.1271835', expected '5276.1271835', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1530ms
memory: 5024kb
input:
19121 34 288 1 30000 8 213 5200 10 169 5148 6 228 5033 11 83 5151 10 98 5200 10 228 5124 7 111 5091 9 218 5114 9 115 5198 10 142 5027 10 221 5105 7 201 5191 10 153 5002 7 130 5186 11 131 5116 10 115 5030 9 124 5053 9 225 5039 10 100 5109 9 170 5202 9 220 5125 11 187 5056 12 115 5062 9 218 5103 6 139...
output:
5092.99345214886488975026
result:
ok found '5092.9934521', expected '5092.9934521', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1728ms
memory: 4188kb
input:
6753 181 9 3 10000 13 948 5040 22 140 5020 10 265 5037 24 1021 5027 12 841 5081 15 202 5034 15 606 5052 11 140 5040 12 1071 5025 9 1045 5022 23 504 5026 19 1213 5085 24 839 5075 12 549 5080 23 643 5025 15 434 5070 25 578 5007 10 132 5030 16 335 5034 21 329 5085 8 239 5084 22 447 5082 26 168 5004 22 ...
output:
5067.16990316355986578856
result:
ok found '5067.1699032', expected '5067.1699032', error '0.0000000'
Test #7:
score: 0
Accepted
time: 687ms
memory: 4348kb
input:
0 3 4 1000 30 36 868 5560 34 896 5226 34 867 5493 32 818 5036 34 1012 5202 37 1136 5475 36 1110 5146 30 1128 5199 33 912 5218 33 903 5398 36 786 5018 37 744 5551 30 997 5120 35 826 5484 32 1133 5300 35 783 5294 32 840 5119 36 958 5186 36 798 5115 37 981 5482 37 792 5390 32 888 5120 31 794 5065 35 99...
output:
5560.13149716685438761488
result:
ok found '5560.1314972', expected '5560.1314972', error '0.0000000'
Test #8:
score: 0
Accepted
time: 931ms
memory: 4144kb
input:
9 14 904 1000 30 19 1145 5166 18 1182 5021 19 1180 5041 20 1146 5163 20 1021 5052 21 1143 5109 19 1225 5138 19 1097 5122 20 1145 5092 20 1197 5133 20 1199 5062 19 1186 5072 21 995 5098 21 1177 5006 20 1151 5203 19 930 5085 18 967 5133 19 1096 5162 16 1015 4995 17 1075 4996 17 1034 4960 17 1053 4796 ...
output:
5134.79727482462112675421
result:
ok found '5134.7972748', expected '5134.7972748', error '0.0000000'
Test #9:
score: 0
Accepted
time: 640ms
memory: 4268kb
input:
14 444 713 1000 30 10 587 5144 11 456 5211 10 562 5395 11 657 5334 11 230 5528 11 535 5015 11 229 5650 11 704 5053 11 351 5050 10 310 5345 14 605 4341 14 478 4275 14 663 4968 14 208 4322 14 456 4635 14 558 4747 14 223 4216 14 233 4272 14 372 4379 14 304 4711 14 327 4475 14 464 4193 14 502 4208 14 69...
output:
5665.28947467679427063558
result:
ok found '5665.2894747', expected '5665.2894747', error '0.0000000'
Test #10:
score: 0
Accepted
time: 535ms
memory: 4152kb
input:
16 4 379 1000 30 4 8 5144 4 8 5131 2 9 5139 4 7 5152 2 9 5145 4 9 5114 4 8 5132 4 7 5145 3 9 5144 4 9 5143 2 9 5136 4 8 5128 4 7 5152 2 9 5115 2 8 5128 2 7 5100 2 7 5099 2 7 5034 2 9 5071 2 8 5057 2 9 5020 2 7 5120 2 8 5057 2 6 5026 2 7 5052 2 7 5133 2 8 5095 2 8 5025 2 8 5106 4 9 5079 30 4 9 5117 2...
output:
5196.17430337664336548187
result:
ok found '5196.1743034', expected '5196.1743034', error '0.0000000'
Test #11:
score: 0
Accepted
time: 895ms
memory: 4268kb
input:
8 165 3003 1000 30 2 22 9259 2 21 9408 2 22 9318 2 22 9939 2 21 9858 2 22 9766 2 22 9794 2 21 9338 2 22 8842 2 22 9722 2 21 9411 2 22 9413 2 22 9020 2 22 8864 2 22 9804 2 22 9124 2 21 9076 2 22 8941 2 21 9439 1 21 9766 1 22 9358 1 21 9604 1 22 9259 1 21 9364 1 21 9259 1 21 9609 1 22 9787 4 22 6050 4...
output:
9856.80496381950979412068
result:
ok found '9856.8049638', expected '9856.8049638', error '0.0000000'
Test #12:
score: 0
Accepted
time: 493ms
memory: 4152kb
input:
15 33 2 1000 30 26 2 5855 26 2 5928 25 2 5874 25 2 5920 27 2 5846 25 2 5793 26 2 5860 24 2 5829 24 2 5866 27 2 5881 23 2 5912 25 2 5907 25 2 5874 24 2 5888 26 1 5925 23 2 5790 22 1 5816 27 1 5840 27 1 5820 24 1 5790 22 1 5907 25 1 5901 24 2 5821 25 1 5903 24 1 5836 24 1 5794 22 1 5806 22 1 5805 25 1...
output:
7056.00000215209638554370
result:
ok found '7056.0000022', expected '7056.0000000', error '0.0000000'
Test #13:
score: 0
Accepted
time: 651ms
memory: 4592kb
input:
19 41 23 750 40 394 21 5250 406 23 5060 350 22 5163 411 22 5225 316 22 5026 307 21 5200 314 23 5067 377 23 5200 316 22 5054 328 21 5279 395 23 5082 335 22 5257 386 22 5049 392 22 5211 405 22 5241 385 22 5083 331 23 5225 326 21 5039 320 22 5067 363 21 5023 7326 24 4988 7868 21 4725 8817 22 4765 7705 ...
output:
5269.66450045129931822885
result:
ok found '5269.6645005', expected '5269.6645005', error '0.0000000'
Test #14:
score: 0
Accepted
time: 1266ms
memory: 4208kb
input:
8 1 557 600 50 7 293 8430 2 298 8231 5 292 5759 2 293 8136 6 297 9014 1 300 8541 5 293 8855 4 293 8436 6 296 8634 6 289 5459 6 295 7969 2 295 8820 6 290 7733 3 290 6007 3 295 5623 6 298 5223 5 296 8289 3 295 9073 4 295 9418 5 290 5124 5 288 6162 4 293 6674 8 297 8322 6 299 5438 7 294 7396 3 291 6810...
output:
7902.23359853508009109646
result:
ok found '7902.2335985', expected '7902.2335985', error '0.0000000'
Test #15:
score: 0
Accepted
time: 789ms
memory: 4760kb
input:
13 60 10 454 66 9 20 5015 14 20 5339 16 18 5419 11 19 5612 5 20 5243 11 19 5564 13 18 5096 15 21 5028 18 20 5506 17 21 5339 8 18 5558 12 19 5219 12 19 5210 8 18 5406 4 20 5213 14 20 5226 10 21 5188 8 21 5096 7 18 5200 11 20 5121 4 20 5581 8 18 5254 16 22 5277 18 21 5127 11 18 5467 13 20 5328 12 18 5...
output:
5607.15346564260107697919
result:
ok found '5607.1534656', expected '5607.1534656', error '0.0000000'
Test #16:
score: 0
Accepted
time: 1105ms
memory: 4200kb
input:
75 8 1393 300 100 11 1461 5036 17 1523 5050 11 1464 5029 12 1463 5056 14 1524 5020 14 1439 5043 13 1506 5020 15 1474 5043 14 1507 5041 14 1432 5045 11 1466 5071 13 1452 5023 17 1491 5058 15 1508 5049 11 1485 5054 15 1499 5019 15 1478 5071 13 1515 5036 16 1518 5037 16 1464 5042 11 1472 5069 12 1456 5...
output:
5045.21830678275000536814
result:
ok found '5045.2183068', expected '5045.2183068', error '0.0000000'
Test #17:
score: 0
Accepted
time: 403ms
memory: 4636kb
input:
10 61 63 857 35 2 12 5264 2 12 5302 2 11 5310 2 12 5306 2 13 5274 3 10 5247 2 13 5324 2 13 5229 2 13 5277 2 10 5282 2 13 5296 3 8 5284 2 13 5293 2 11 5246 2 10 5302 2 11 5261 2 12 5274 2 11 5316 2 11 5249 2 13 5241 2 12 5299 3 12 5305 2 12 5294 3 8 5250 3 4 5314 3 6 5228 2 3 5291 2 2 5322 2 2 5282 2...
output:
5477.24966662199767597485
result:
ok found '5477.2496666', expected '5477.2496666', error '0.0000000'
Test #18:
score: 0
Accepted
time: 606ms
memory: 4608kb
input:
20 6499 1 810 37 1173 102 6510 1524 103 6174 1412 103 6566 1418 102 6549 1580 105 6513 1305 103 6151 1606 103 6385 1491 104 6060 1783 105 6582 1522 105 6554 1488 105 6496 1614 104 5964 1803 104 6298 1326 103 6358 1248 103 6605 1462 102 6441 1410 103 6212 1666 103 5414 1351 104 5659 1767 105 5750 976...
output:
6864.00006234988359210547
result:
ok found '6864.0000623', expected '6864.0000000', error '0.0000000'
Test #19:
score: 0
Accepted
time: 429ms
memory: 4572kb
input:
29 1 207 652 46 1 228 5064 2 135 5006 1 460 5063 2 166 5014 1 289 5066 2 252 5010 2 156 5031 1 172 5056 2 212 5012 1 236 5021 1 389 5054 1 180 5037 2 320 5025 1 427 5067 2 406 5019 2 393 5015 2 315 4913 2 401 4941 2 409 4901 2 372 4947 2 133 4895 2 253 4973 2 274 4975 2 177 4899 2 151 4966 2 178 489...
output:
5046.73837829585681902245
result:
ok found '5046.7383783', expected '5046.7383783', error '0.0000000'
Test #20:
score: 0
Accepted
time: 748ms
memory: 4280kb
input:
12 98 1270 555 54 4 9584 5092 4 5683 5016 6 4181 5027 5 4947 5033 6 7472 5059 5 9397 5055 6 8711 5094 6 5931 5047 6 3019 5010 6 9526 5048 4 6277 5024 4 3570 5062 4 6652 5001 6 2956 5005 4 3401 5100 4 7844 5096 4 2178 5011 6 2925 5111 4 4989 5004 6 5362 5015 6 8080 5017 6 3530 5048 6 5457 5016 6 5795...
output:
5074.32475070777036307845
result:
ok found '5074.3247507', expected '5074.3247507', error '0.0000000'
Test #21:
score: 0
Accepted
time: 1228ms
memory: 4496kb
input:
29 3 55 400 75 1 36 5624 2 36 5515 2 37 5425 2 36 5593 2 36 5225 1 37 5066 2 36 5120 2 37 5296 1 36 5378 2 37 5676 2 36 5573 2 36 5687 2 38 5431 1 38 5071 2 37 5971 2 36 5052 2 38 5307 2 38 5213 2 37 5528 2 35 5103 2 38 5597 2 38 5389 2 37 5293 2 38 5047 1 37 5414 1 37 5479 2 36 5885 1 36 5051 1 36 ...
output:
5593.63848435010550019797
result:
ok found '5593.6384844', expected '5593.6384844', error '0.0000000'
Test #22:
score: 0
Accepted
time: 1661ms
memory: 4228kb
input:
916 125 544 2 15000 2 25 5097 2 38 5158 1 40 5142 2 31 5163 1 42 5181 2 26 5148 1 31 5186 2 26 5171 1 33 5182 2 24 5189 2 29 5063 1 32 5093 2 31 5148 1 36 5090 2 30 5117 2 28 5143 1 39 5165 1 40 5105 2 31 5084 1 37 5119 1 23 5106 1 34 5137 2 38 5171 1 33 5084 2 36 5118 2 37 5064 1 38 5062 1 37 5171 ...
output:
5162.41857566530597978272
result:
ok found '5162.4185757', expected '5162.4185757', error '0.0000000'
Test #23:
score: 0
Accepted
time: 653ms
memory: 4164kb
input:
41 1357 7 600 50 15 1919 5615 13 1856 5644 17 1623 5495 17 1613 5296 2472 1424 4670 2568 1913 4538 2799 1500 4369 2841 1419 4480 2554 1619 4623 2647 1955 4782 2392 1740 4921 2854 1465 4753 2338 1981 4192 2550 1930 4942 2613 1688 4925 2349 1782 4844 2681 1877 4628 2655 1700 4659 2414 1781 4433 2826 1...
output:
5764.38583632130576006602
result:
ok found '5764.3858363', expected '5764.3858363', error '0.0000000'
Test #24:
score: 0
Accepted
time: 544ms
memory: 4440kb
input:
53 252 359 555 54 517 48 6179 89 48 5942 212 48 5955 291 50 6032 141 49 6176 264 48 5980 45 49 5942 394 49 5944 129 48 6081 232 48 6025 372 49 5916 268 47 6121 281 48 6186 465 49 6172 396 49 5984 316 48 5916 210 49 6154 425 48 5913 249 48 6022 155 49 6189 531 49 5951 396 49 6097 347 47 6009 357 48 6...
output:
9908.00000514280327479355
result:
ok found '9908.0000051', expected '9908.0000000', error '0.0000000'
Test #25:
score: 0
Accepted
time: 826ms
memory: 4584kb
input:
9 253 1242 454 66 3 85 5083 3 90 5076 3 85 5072 4 82 5097 3 89 5088 3 88 5086 4 85 5104 3 87 5073 3 87 5095 3 90 5101 4 90 5075 3 85 5101 4 87 5064 3 84 5096 3 84 5104 3 85 5086 3 86 5098 3 84 5071 3 89 5106 3 87 5106 3 88 5077 3 87 5071 3 89 5107 3 82 5091 4 84 5102 4 87 5093 4 88 5082 4 87 5106 4 ...
output:
5147.91400007528227433795
result:
ok found '5147.9140001', expected '5147.9140001', error '0.0000000'
Test #26:
score: 0
Accepted
time: 544ms
memory: 4348kb
input:
13 299 33 400 75 2 22 5261 2 24 5184 2 24 5272 3 23 5181 2 23 4730 2 23 4939 2 23 5022 2 24 5085 2 22 4956 2 23 4876 2 23 4789 2 24 5018 2 23 4880 2 23 5008 2 23 5106 2 23 4612 2 22 4961 3 22 5101 3 24 4684 3 23 4909 3 23 5029 3 23 5010 3 24 5100 3 23 4713 3 25 4768 3 23 4802 3 22 4747 3 23 4615 3 2...
output:
5347.22332929868935025297
result:
ok found '5347.2233293', expected '5347.2233293', error '0.0000000'
Test #27:
score: 0
Accepted
time: 1190ms
memory: 4400kb
input:
17 933 45 300 100 10 84 5348 11 85 5343 9 91 5327 11 86 5401 7 87 5474 10 85 5410 10 92 5313 10 89 5466 8 89 5424 12 91 5379 9 87 5326 11 88 5433 10 91 5467 11 90 5384 11 86 5504 8 91 5397 8 89 5428 8 85 5447 11 87 5432 7 91 5503 9 90 5475 8 88 5481 9 86 5502 12 86 5463 9 88 5355 10 87 5313 10 90 54...
output:
5535.48914508548114099540
result:
ok found '5535.4891451', expected '5535.4891451', error '0.0000000'
Test #28:
score: -100
Time Limit Exceeded
input:
3494 16 104 1 30000 2 1783 1419 1 1777 1518 2 1747 1641 1 1787 1397 1 1782 1484 2 1756 1668 3 1792 1684 1 1732 1747 3 1780 1486 1 1776 1368 1 1721 1735 2 1706 1354 3 1751 1376 2 1781 1747 2 1714 1380 4 1789 1529 2 1733 1428 4 1734 1464 2 1750 1597 2 1794 1361 2 1766 1455 1 1755 1535 3 1704 1428 3 17...
output:
1558.68511683019414704177