QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#733735#5978. Runaway Quailtanjunming0 804ms5284kbC++142.0kb2024-11-10 20:43:172024-11-10 20:43:18

Judging History

你现在查看的是最新测评结果

  • [2024-11-10 20:43:18]
  • 评测
  • 测评结果:0
  • 用时:804ms
  • 内存:5284kb
  • [2024-11-10 20:43:17]
  • 提交

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;
}

详细

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)