QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#312532 | #8137. 'Ello, and What Are You After, Then? | Kevin5307 | TL | 1625ms | 5072kb | C++23 | 2.1kb | 2024-01-23 22:56:40 | 2024-01-23 22:56: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=1e-6,r=1e6;
for(int i=0;i<30;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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3740kb
input:
0 1 6 2 1 1 1 1 2 1 10 1 1 10 10
output:
7.00000001883083200482
result:
ok found '7.0000000', expected '7.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
2 1 2 1 4 10 2 1 10 1 1 1 10 1 1 1 10
output:
5.90909095521396920958
result:
ok found '5.9090910', expected '5.9090909', error '0.0000000'
Test #3:
score: 0
Accepted
time: 784ms
memory: 4412kb
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.36457905314023264509
result:
ok found '1453.3645791', expected '1453.3645790', error '0.0000000'
Test #4:
score: 0
Accepted
time: 811ms
memory: 4984kb
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.12718345551456877729
result:
ok found '5276.1271835', expected '5276.1271835', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1238ms
memory: 5072kb
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: 1323ms
memory: 4060kb
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.16990316400369920302
result:
ok found '5067.1699032', expected '5067.1699032', error '0.0000000'
Test #7:
score: 0
Accepted
time: 635ms
memory: 4336kb
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.13149727441214054124
result:
ok found '5560.1314973', expected '5560.1314972', error '0.0000000'
Test #8:
score: 0
Accepted
time: 687ms
memory: 4128kb
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.79727485188777791336
result:
ok found '5134.7972749', expected '5134.7972748', error '0.0000000'
Test #9:
score: 0
Accepted
time: 573ms
memory: 4084kb
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.28947513056391471764
result:
ok found '5665.2894751', expected '5665.2894747', error '0.0000000'
Test #10:
score: 0
Accepted
time: 386ms
memory: 4264kb
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.17430337948644591961
result:
ok found '5196.1743034', expected '5196.1743034', error '0.0000000'
Test #11:
score: 0
Accepted
time: 651ms
memory: 4336kb
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.80496386675986286718
result:
ok found '9856.8049639', expected '9856.8049638', error '0.0000000'
Test #12:
score: 0
Accepted
time: 352ms
memory: 4128kb
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: 629ms
memory: 4444kb
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.66450046195677714422
result:
ok found '5269.6645005', expected '5269.6645005', error '0.0000000'
Test #14:
score: 0
Accepted
time: 884ms
memory: 4328kb
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.23359858703861391405
result:
ok found '7902.2335986', expected '7902.2335985', error '0.0000000'
Test #15:
score: 0
Accepted
time: 741ms
memory: 4688kb
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.15346565796608047094
result:
ok found '5607.1534657', expected '5607.1534656', error '0.0000000'
Test #16:
score: 0
Accepted
time: 818ms
memory: 4380kb
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.21830678479273046833
result:
ok found '5045.2183068', expected '5045.2183068', error '0.0000000'
Test #17:
score: 0
Accepted
time: 392ms
memory: 4400kb
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.24966662466249545105
result:
ok found '5477.2496666', expected '5477.2496666', error '0.0000000'
Test #18:
score: 0
Accepted
time: 446ms
memory: 4620kb
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: 413ms
memory: 4364kb
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.73837830082993605174
result:
ok found '5046.7383783', expected '5046.7383783', error '0.0000000'
Test #20:
score: 0
Accepted
time: 699ms
memory: 4156kb
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.32475070865802990738
result:
ok found '5074.3247507', expected '5074.3247507', error '0.0000000'
Test #21:
score: 0
Accepted
time: 847ms
memory: 4532kb
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.63848435054933361243
result:
ok found '5593.6384844', expected '5593.6384844', error '0.0000000'
Test #22:
score: 0
Accepted
time: 1330ms
memory: 4328kb
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: 610ms
memory: 4392kb
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.38583634741917194333
result:
ok found '5764.3858363', expected '5764.3858363', error '0.0000000'
Test #24:
score: 0
Accepted
time: 387ms
memory: 4480kb
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: 570ms
memory: 4372kb
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.91400007563788676634
result:
ok found '5147.9140001', expected '5147.9140001', error '0.0000000'
Test #26:
score: 0
Accepted
time: 409ms
memory: 4680kb
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.22332934913720237091
result:
ok found '5347.2233293', expected '5347.2233293', error '0.0000000'
Test #27:
score: 0
Accepted
time: 801ms
memory: 4524kb
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.48914508752386609558
result:
ok found '5535.4891451', expected '5535.4891451', error '0.0000000'
Test #28:
score: 0
Accepted
time: 1625ms
memory: 5012kb
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
result:
ok found '1558.6851168', expected '1558.6851168', error '0.0000000'
Test #29:
score: -100
Time Limit Exceeded
input:
1677 6852 12 1 30000 9 87 9481 10 93 9229 10 85 9558 10 95 9542 10 95 8929 8 84 9878 10 87 9347 9 98 9646 8 89 9525 8 93 9345 8 93 9841 9 89 9598 10 95 9250 10 96 9733 8 94 9521 10 95 8888 9 92 9157 10 91 9802 8 94 9395 8 95 9691 8 94 9290 9 85 9981 8 91 9804 8 93 9520 10 87 9238 8 92 9640 10 94 998...