QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#765294 | #8266. Astronomer | Pioneer# | 0 | 1068ms | 6072kb | C++20 | 1.8kb | 2024-11-20 13:43:26 | 2024-11-20 13:43:33 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define lb lower_bound
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define in insert
#define sz(s) (int)s.size()
#define ppb pop_back
#define mem(a,i) memset(a,i,sizeof(a))
#define int ll
using namespace std;
const int MAX=700+10;
const int inf=2e18;
const int mod=1e9+7;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,k,s,t;
int x[MAX],y[MAX];
ld dp[MAX][MAX];
ld dist(ld a,ld b,ld c,ld d){
return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
ld getY(ld X,ld Y){
for(int i=0;i<=n;i++)for(int j=0;j<=k;j++)dp[i][j]=inf;
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
dp[i][j]=dp[i-1][j];
dp[i][j]=min(dp[i][j],max(dp[i-1][j-1],dist(X,Y,x[i],y[i])));
}
}
return t*dp[n][k]+s*dist(0,0,X,Y);
}
ld get(ld x){
ld l=-1e9,r=1e9;
for(int i=1;i<=200;i++){
ld m1=l+(r-l)/3,m2=r-(r-l)/3;
if(getY(x,m1)<=getY(x,m2))r=m2;
else l=m1;
}
return getY(x,l);
}
void solve(){
cin>>k>>n>>s>>t;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
ld l=-1e9,r=1e9;
for(int i=1;i<=200;i++){
ld m1=l+(r-l)/3,m2=r-(r-l)/3;
if(get(m1)<=get(m2))r=m2;
else l=m1;
}
cout.precision(10);
// for(int i=0;i<=10;i++)cout<<get(i)<<"\n";
// cout<<fixed<<get(5)<<"\n";
cout<<fixed<<get(l)<<"\n";
}
signed main(){
// freopen("escape.in","r",stdin);
// freopen("escape.out","w",stdout);
ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 8
Accepted
time: 338ms
memory: 4136kb
input:
5 50 100 10 83800992 -886133390 419292091 -739946592 23316601 -533703422 728805984 890308742 -66894195 66628784 154560403 -595148422 -827958439 928301296 849961738 946067907 310878751 -114000318 871656204 66733904 -791356839 125420374 -838471381 157736324 -911519472 -679917398 816843257 -363318953 -...
output:
4930145422.6525176312
result:
ok found '4930145422.6525173', expected '4930145422.6525173', error '0.0000000'
Test #2:
score: 8
Accepted
time: 580ms
memory: 4124kb
input:
10 50 100 10 -793680088 284470669 115693879 -170843456 -154728667 217328790 907384174 843374520 253755807 -38186295 -381212540 -292308497 -867806770 -491743910 -913208139 289193728 195163552 -826028088 -877650578 -170991023 568907081 -881381181 -199872307 265851943 589436960 69367477 -611624975 1225...
output:
4803824081.6213348205
result:
ok found '4803824081.6213350', expected '4803824081.6213350', error '0.0000000'
Test #3:
score: 8
Accepted
time: 1062ms
memory: 4184kb
input:
20 50 100 100 187033242 -158211473 423007364 -836894730 -907522970 960081589 -480988812 653654390 597700121 -67379126 -460065669 -241034985 913656927 -606901580 -200092163 -116008540 573697247 -406354383 317815409 37136086 -865167374 -612614868 -9287623 170008780 -819856 614614372 -709291610 -711283...
output:
63648024908.3917985037
result:
ok found '63648024908.3917999', expected '63648024908.3917999', error '0.0000000'
Test #4:
score: 8
Accepted
time: 1068ms
memory: 4128kb
input:
20 50 1000000000 1000000000 347048005 -530364556 -904966175 -633735536 396657069 818647482 569030381 446734190 -656658950 -638699736 253688651 -31470973 85886754 807760345 -248598849 -277622783 -64735947 66844493 -890915586 -244816739 -488396456 -969658430 664980418 -352719175 -960264172 611250021 4...
output:
704682191270371226.8125000000
result:
ok found '704682191270371200.0000000', expected '704682191270371200.0000000', error '0.0000000'
Test #5:
score: 8
Accepted
time: 580ms
memory: 4152kb
input:
10 50 10 2 0 -21855775 0 -15981466 0 -16102820 0 -7780900 0 74497379 0 -40221537 0 -89726059 0 52785260 0 86230474 0 70697695 0 -80396368 0 86433127 0 -22696494 0 -54630396 0 29917934 0 -5750238 0 30414580 0 -17223080 0 -41581695 0 13697626 0 64151962 0 -10413226 0 -24542977 0 -33200412 0 -66362775 ...
output:
31962932.0000000000
result:
ok found '31962932.0000000', expected '31962932.0000000', error '0.0000000'
Test #6:
score: 8
Accepted
time: 580ms
memory: 4124kb
input:
10 50 20 3 -54614756 0 54949544 0 96550412 0 38271729 0 -35136806 0 -92782941 0 30777752 0 -82904205 0 4689998 0 -91407242 0 97692736 0 -7455904 0 -6467000 0 -2811702 0 -28270423 0 96066983 0 -52546488 0 21369820 0 52638665 0 62720370 0 44623271 0 72875104 0 57256607 0 -64867652 0 -19068967 0 142894...
output:
50675835.0000000000
result:
ok found '50675835.0000000', expected '50675835.0000000', error '0.0000000'
Test #7:
score: 8
Accepted
time: 576ms
memory: 6024kb
input:
10 50 40 8 12345 -52897048 12345 -88342117 12345 -70698612 12345 59534976 12345 -10071874 12345 -46454456 12345 -8778454 12345 33361098 12345 45415305 12345 -20707863 12345 -35952217 12345 97544665 12345 -27016480 12345 -94696906 12345 92805171 12345 -23291640 12345 87319050 12345 -89851825 12345 64...
output:
165662933.4379022036
result:
ok found '165662933.4379022', expected '165662933.4379022', error '0.0000000'
Test #8:
score: 8
Accepted
time: 577ms
memory: 4000kb
input:
10 50 80 4 -66610775 54321 -51714569 54321 66822467 54321 -98768070 54321 -65322728 54321 87093234 54321 -46782416 54321 -83441680 54321 42037863 54321 42415504 54321 -80735005 54321 -45311373 54321 -52041933 54321 69039381 54321 74795305 54321 11699205 54321 62686218 54321 -97355638 54321 -82839140...
output:
145213750.5616131382
result:
ok found '145213750.5616131', expected '145213750.5616131', error '0.0000000'
Test #9:
score: 8
Accepted
time: 580ms
memory: 4136kb
input:
10 50 50 27 4043107 -4042907 7200519 -7200319 -6116699 6116899 -4124247 4124447 6438015 -6437815 -8254791 8254991 -1974217 1974417 7542063 -7541863 -1546732 1546932 -539320 539520 -5158206 5158406 1377811 -1377611 -7606954 7607154 1705751 -1705551 9238418 -9238218 -772806 773006 7984019 -7983819 -85...
output:
52606194.8318030127
result:
ok found '52606194.8318030', expected '52606194.8318030', error '0.0000000'
Test #10:
score: 8
Accepted
time: 580ms
memory: 6004kb
input:
10 50 33 27 3711782 3711782 -2567030 -2567030 3945872 3945872 3622687 3622687 8906914 8906914 -9014274 -9014274 -5514887 -5514887 6198091 6198091 -1558344 -1558344 6281940 6281940 2751778 2751778 7991511 7991511 -6015675 -6015675 -2486513 -2486513 -9506702 -9506702 6962924 6962924 -2098352 -2098352 ...
output:
103995358.2068673775
result:
ok found '103995358.2068674', expected '103995358.2068674', error '0.0000000'
Test #11:
score: 0
Time Limit Exceeded
input:
50 499 100 10 -268214856 -800550919 411903188 -773971831 769567597 -734212705 -55581201 -530714034 835073201 -469918138 -367731605 691744277 844219796 994636033 -488959612 991190069 -588779840 21455475 66709215 657587786 518510010 -907735337 -306396571 -841924090 477919418 633359061 -616931925 43650...
output:
result:
Subtask #2:
score: 0
Time Limit Exceeded
Test #14:
score: 0
Time Limit Exceeded
input:
50 50 0 100 -636373727 151906670 -436420422 -967929931 -946894101 -648810265 -318412226 -368156635 608567780 -787997497 40618170 966479708 -451370311 -406325088 830840722 -678655131 -89071166 -21371001 60891837 -615893965 785687617 -623669416 -513873386 -653229486 -555272924 350850129 -901712781 -32...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Time Limit Exceeded
Test #214:
score: 15
Accepted
time: 335ms
memory: 4132kb
input:
5 50 100 10 460309761 -799742665 -100987677 761175444 -361900447 -449675625 -631196407 -1559607 -721861391 643436364 -122962913 5884730 295248578 491223378 986298998 468191512 -169039995 374919122 -46710929 402201182 -943494268 -547915393 521170382 929707215 355890998 688700401 -264192618 -469266213...
output:
3882365967.1217989526
result:
ok found '3882365967.1217990', expected '3882365967.1217990', error '0.0000000'
Test #215:
score: 15
Accepted
time: 580ms
memory: 4000kb
input:
10 50 100 10 -59322388 -550771605 390341986 606931103 -871418394 -988685394 580794497 -673520982 343709833 -956039479 801247869 439625461 1589381 489746876 -665908093 867949899 -814872010 -882744429 972183850 -174063671 -943257937 -948482354 661478192 -170778975 168727345 625941217 886063094 6424373...
output:
6482833671.2443125439
result:
ok found '6482833671.2443123', expected '6482833671.2443123', error '0.0000000'
Test #216:
score: 15
Accepted
time: 1066ms
memory: 4144kb
input:
20 50 100 100 172256526 346633307 259229223 982272224 -14693453 726686801 112585283 412740894 -612981746 330560232 414925589 952297853 755222897 -470278963 -980948426 -178972652 -824953309 -812890315 -898120945 157273649 303641707 -605295618 604348064 -811746991 -588454314 639747671 -26677205 -49086...
output:
78688279609.2232165858
result:
ok found '78688279609.2232208', expected '78688279609.2232208', error '0.0000000'
Test #217:
score: 15
Accepted
time: 581ms
memory: 4128kb
input:
10 50 10 2 0 -35903531 0 -55854088 0 -25941394 0 89068915 0 -7247589 0 -64772890 0 -80596681 0 92477857 0 48897135 0 48388667 0 79862347 0 -34613254 0 -84838669 0 71155967 0 -47166258 0 87774674 0 -66532036 0 6427675 0 71979570 0 66924791 0 77107874 0 -33156614 0 28490657 0 -90526831 0 83631701 0 -1...
output:
58462844.0000000000
result:
ok found '58462844.0000000', expected '58462844.0000000', error '0.0000000'
Test #218:
score: 15
Accepted
time: 580ms
memory: 3944kb
input:
10 50 20 3 -57784739 0 32680665 0 -40372843 0 -38112740 0 -27483733 0 49180445 0 -33865310 0 -93275213 0 14582688 0 49726688 0 23692784 0 5079108 0 21787036 0 -55152691 0 -58030794 0 -52226157 0 -9501633 0 60816120 0 -23437675 0 47108333 0 50375350 0 -26261536 0 -45729813 0 53836456 0 58692596 0 -61...
output:
66153075.0000000000
result:
ok found '66153075.0000000', expected '66153075.0000000', error '0.0000000'
Test #219:
score: 15
Accepted
time: 580ms
memory: 4148kb
input:
10 50 40 8 12345 12323649 12345 11519440 12345 24159195 12345 -57111032 12345 53702723 12345 95759380 12345 -37949320 12345 -57561177 12345 85915543 12345 65350403 12345 20774339 12345 -3634719 12345 19876856 12345 44106551 12345 -58364224 12345 97902750 12345 -75785099 12345 -67707690 12345 3160736...
output:
159014878.6686349801
result:
ok found '159014878.6686350', expected '159014878.6686350', error '0.0000000'
Test #220:
score: 15
Accepted
time: 573ms
memory: 6072kb
input:
10 50 80 4 -70238808 54321 24137760 54321 41312535 54321 -69086917 54321 -36898127 54321 14009199 54321 56929308 54321 11184746 54321 66393315 54321 64719362 54321 85675548 54321 95371409 54321 61535731 54321 -52520731 54321 45109035 54321 -14483607 54321 9218985 54321 68104038 54321 67771674 54321 ...
output:
74235913.9891998097
result:
ok found '74235913.9891998', expected '74235913.9891998', error '0.0000000'
Test #221:
score: 15
Accepted
time: 581ms
memory: 6072kb
input:
10 50 50 27 3279583 -3279383 8496141 -8495941 2560388 -2560188 9634192 -9633992 -2552975 2553175 -7911684 7911884 2838580 -2838380 -7775713 7775913 3741574 -3741374 9177121 -9176921 8637231 -8637031 -5882031 5882231 4583792 -4583592 -7867752 7867952 2459405 -2459205 1339089 -1338889 -7573744 7573944...
output:
66485039.2166310450
result:
ok found '66485039.2166310', expected '66485039.2166310', error '0.0000000'
Test #222:
score: 15
Accepted
time: 580ms
memory: 3996kb
input:
10 50 33 27 4487102 4487102 6221683 6221683 1830397 1830397 5936217 5936217 -7057367 -7057367 -8795014 -8795014 -8413252 -8413252 6245638 6245638 9517562 9517562 -9340337 -9340337 3797596 3797596 7290956 7290956 -3389901 -3389901 1035768 1035768 -5990751 -5990751 7763163 7763163 4644377 4644377 2357...
output:
73730332.3728779077
result:
ok found '73730332.3728779', expected '73730332.3728779', error '0.0000000'
Test #223:
score: 0
Time Limit Exceeded
input:
50 499 100 10 -749368701 366767459 193967555 -903497290 -182275959 325815353 -235814193 526168810 -620430207 -783595025 950735951 -211615552 542199384 -938659076 610443494 -211771002 79213172 -984926414 911591362 438385925 179894037 -508420372 -402114614 -602093047 -262347653 762564982 -529492250 -2...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
0%