QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#733539#5978. Runaway Quaildygxczn23 ✓2768ms8552kbC++141.6kb2024-11-10 19:45:132024-11-10 19:45:17

Judging History

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

  • [2024-11-10 19:45:17]
  • 评测
  • 测评结果:23
  • 用时:2768ms
  • 内存:8552kb
  • [2024-11-10 19:45:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int N=501;
const ld INF=1e15;
int C,n,p[N];
ld f[N][N];
struct node{ld a,b;}a[N],b[N],c[N];
void solve()
{
    cin>>C>>n;
    for(int i=1;i<=n;i++) cin>>a[i].a;
    for(int i=1;i<=n;i++) cin>>a[i].b;
    sort(a+1,a+1+n,[](node a,node b){return a.a<b.a;});
    int p1=0,p2=0;
    while(p1<n&&a[p1+1].a<0) p1++,b[p1]={a[p1].a,-a[p1].b};
    p2=n-p1;
    for(int i=p1+1;i<=n;i++) c[i-p1]=a[i];
    sort(b+1,b+1+p1,[](node a,node b){return a.b<b.b;});
    sort(c+1,c+1+p2,[](node a,node b){return a.b>b.b;});
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) f[i][j]=INF;
    f[0][0]=0;
    for(int i=0;i<=p1;i++){
        for(int j=0;j<=p2;j++){
            if(i==p1&&j==p2) continue;
            ld maxtim=0;
            for(int k=i+1;k<=p1;k++){
                maxtim=max(maxtim,-(b[k].a+b[k].b*f[i][j])/(b[k].b+C));
                if(k==p1&&j==p2) f[k][j]=min(f[k][j],f[i][j]+maxtim);
                else f[k][j]=min(f[k][j],f[i][j]+2*maxtim);
            }
            maxtim=0;
            for(int k=j+1;k<=p2;k++){
                maxtim=max(maxtim,(c[k].a+c[k].b*f[i][j])/(C-c[k].b));
                if(k==p2&&i==p1) f[i][k]=min(f[i][k],f[i][j]+maxtim);
                else f[i][k]=min(f[i][k],f[i][j]+2*maxtim);
            }
        }
    }
    cout<<fixed<<setprecision(114514)<<f[p1][p2]<<"\n";
}
int main()
{
    // freopen("tiii.in","r",stdin);
    // freopen("tiii.out","w",stdout);
    int T;
    cin.tie(0)->sync_with_stdio(0);
    cin>>T;
    for(int i=1;i<=T;i++) cout<<"Case #"<<i<<": ",solve();
}

詳細信息

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 121ms
memory: 8504kb

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:

Case #1: 3.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok correct! (50 test cases)

Subtask #2:

score: 15
Accepted

Test #2:

score: 15
Accepted
time: 2768ms
memory: 8552kb

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:

Case #1: 3.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok correct! (50 test cases)

Extra Test:

score: 0
Extra Test Passed