QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#733735 | #5978. Runaway Quail | tanjunming | 0 | 804ms | 5284kb | C++14 | 2.0kb | 2024-11-10 20:43:17 | 2024-11-10 20:43:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=500;
const double eps=1e-8;
const double inf=1e12;
int T,n,t1,t2;
double C,ans,a[N+5],b[N+5],f[N+5][N+5];
struct pt{
double x,v;
}w1[N+5],w2[N+5];
bool cmp(pt ax,pt bx){
return ax.v<bx.v;
}
bool pd1(int i,int j,double t){
if(!i) return 1;
return w1[i].x+w1[i].v*t>w1[j].x+w1[j].v*t+eps;
}
bool pd2(int i,int j,double t){
if(!i) return 1;
return w2[i].x+w2[i].v*t>w2[j].x+w2[j].v*t+eps;
}
int main()
{
// freopen("tiii.in","r",stdin);
// freopen("tiii.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%lf%d",&C,&n);
t1=t2=0;
for(int i=1;i<=n;i++){
scanf("%lf",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%lf",&b[i]);
if(a[i]<0) w1[++t1]=(pt){-a[i],b[i]};
else w2[++t2]=(pt){a[i],b[i]};
}
sort(w1+1,w1+t1+1,cmp);
sort(w2+1,w2+t2+1,cmp);
for(int i=0;i<=t1;i++){
for(int j=0;j<=t2;j++) f[i][j]=inf;
}
ans=inf;
f[t1][t2]=0;
for(int i=t1;i>=0;i--){
for(int j=t2;j>=0;j--){
double nd=(w1[i].x+w1[i].v*f[i][j])/(C-w1[i].v);
for(int p=i-1;p>=0;p--){
if(pd1(p,i,f[i][j])){
f[p][j]=min(f[p][j],f[i][j]+2*nd);
}
if(p) nd=max(nd,(w1[p].x+w1[p].v*f[i][j])/(C-w1[p].v));
}
if(!j) f[0][0]=min(f[0][0],f[i][j]+nd);
nd=(w2[j].x+w2[j].v*f[i][j])/(C-w2[j].v);
for(int p=j-1;p>=0;p--){
if(pd2(p,j,f[i][j])){
f[i][p]=min(f[i][p],f[i][j]+2*nd);
}
if(p) nd=max(nd,(w2[p].x+w2[p].v*f[i][j])/(C-w2[p].v));
}
if(!i) f[0][0]=min(f[0][0],f[i][j]+nd);
}
}
printf("%.8f\n",f[0][0]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3964kb
input:
50 4 3 -3 -6 -9 3 2 1 2 2 1 -1 1 1 1000 25 769234 -5735820 -524288 -5403090 -6429140 1574982 1 -9733628 -1407481 4093041 4117720 -3193501 -9765195 -3069520 1122216 -5799108 131072 -8482066 -256 -8021159 -8958386 -7027036 5370579 -3602534 -6834567 425 102 744 155 339 19 999 19 159 198 51 304 369 601 ...
output:
3.00000000 5.00000000 51133.93750000 429262.39614211 129368.01227960 7801.83203125 66656.81250000 607220.69042351 5725896.87634409 129205.28522013 64298.00000000 610881.70515971 17621.65625000 129042.96702261 128719.55106516 196692.32268421 218002.25000000 40734.93750000 128881.05614806 451714.41960...
result:
wrong output format Expected 'Case' but found '3.00000000' (test case 1)
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 0
Wrong Answer
time: 804ms
memory: 5284kb
input:
50 4 3 -3 -6 -9 3 2 1 2 2 1 -1 1 1 1000 500 -9650379 9806301 -6495789 -1283284 5022779 4725553 9364178 -8123302 -9609729 7847458 -142364 6983908 8147008 -3186924 7339254 -8737645 8757174 7887319 3609962 5780915 -1752801 -1657946 -9511339 5113995 -7887160 -6093170 260267 -3837106 -356098 6676924 6210...
output:
3.00000000 5.00000000 205911250.08888891 36298.00000000 186002.25000000 13741948.50000000 109001.12500000 38656.81250000 128881.05614806 8069407.98709677 128881.05614806 124955.37500000 128719.55106516 17621.65625000 54188.06250000 129042.96702261 23457.59375000 7792241110.00000000 9267972.46153846 ...
result:
wrong output format Expected 'Case' but found '3.00000000' (test case 1)