QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#733539 | #5978. Runaway Quail | dygxczn | 23 ✓ | 2768ms | 8552kb | C++14 | 1.6kb | 2024-11-10 19:45:13 | 2024-11-10 19:45:17 |
Judging History
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