QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#200369 | #7344. Those Russian Hackers | Delay_for_five_minutes# | AC ✓ | 850ms | 136456kb | C++20 | 3.4kb | 2023-10-04 16:43:07 | 2023-10-04 16:43:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
double p[300005];
int n , k;
double q[600005];
double f[300005];
typedef double db;
const int N = 1<<21 ;
const db pi2 = acos(-1) * 2;
struct cp {
db x,y;
inline cp() {x = y = 0;}
inline cp(db a,db b) {x=a,y=b;}
inline cp operator+(const cp& p) const {return cp(x+p.x , y+p.y) ;}
inline cp operator-(const cp& p) const {return cp(x-p.x , y-p.y) ;}
inline cp operator*(const cp& p) const {return cp(x*p.x - y*p.y, x*p.y + y*p.x) ;}
inline cp conj() {
return cp(x , -y) ;
}
}w[N];
int re[N] ;
inline int getre(int n)
{
int len = 1 , bit = 0;
while(len < n) ++bit , len <<= 1;
for(int i = 1;i < len;i++) re[i] = (re[i>>1]>>1)|((i&1)<<(bit-1)) ;
return len;
}
inline void init0() {
for(int i =0 ;i < N;i++) w[i] = cp(cos(pi2*i/N) , sin(pi2*i/N));
}
void fft(cp *a,int n,int m) {
for(int i = 1;i < n;i++) if(i < re[i]) swap(a[i] , a[re[i]]) ;
for(int k=1,r=N>>1 ; k < n ; k <<= 1 , r >>= 1) {
for(int i = 0;i < n;i+=(k<<1)) {
for(int j = 0;j < k;j++) {
cp &L = a[i + j] , &R = a[i+j+k] , t=w[r*j]*R ;
R = L-t , L=L+t;
}
}
}
if(!~m) {
reverse(a+1,a+n);
cp tmp = cp(1.0/n , 0) ;
for(int i = 0;i < n;i++) a[i] = a[i] * tmp ;
}
return ;
}
double preq[600005];
cp x1[N] , x2[N] ;
double h[300005];
double sufp[300005]; ///后i个p的和
double prepf[300005];
double g[300005]; ///钦定从i开始赢
double wg[300005];
int main()
{
// freopen("in.txt","r",stdin) ;
scanf("%d%d",&n,&k) ;
for(int i = 0;i < n;i++) {scanf("%lf",&p[i]) ; }
for(int i = 1;i <= n*2-2;i++) scanf("%lf",&q[i]) ;
init0() ;
sufp[0] = 0;
for(int i = 1;i <= n;i++) sufp[i] = sufp[i - 1] + p[n - i] ;
for(int i = 0;i <= n;i++) {x1[i].x = sufp[i] ; }
for(int i = n + 1;i <= n*2;i++) x1[i].x = 1.0;
for(int i = 1;i <= n*2-2;i++) x2[i].x = q[i] ;
int s = getre(4*n - 1) ;
fft(x1 , s , 1) ; fft(x2 , s , 1) ;
for(int i = 0;i < s;i++) x1[i] = x1[i] * x2[i] ;
fft(x1 , s , -1);
for(int i = 0;i <= n ;i++) {
// printf("I %d %lf\n",i,x1[i].x) ;
g[n-i] = x1[i].x ;
}
for(int i = n ; i < 2*(n ) ;i++) {
f[n-1-(i - n)] = x1[i].x ;
}
preq[0] = 0;
for(int i = 1;i <= 2*n - 2;i++) preq[i] = preq[i - 1] + q[i] ;
// for(int i = n - 2;i >= 0;i--) g[i] += g[i + 1];
for(int i = 0;i < n ;i++) {
h[k] += p[i] * preq[n-1-i] ;
wg[i] = p[i] * preq[n-1-i];
if(i > 0) wg[i] += wg[i - 1];
}
for(int i = 0;i < n;i++) {
// printf("%lf %lf\n",wg[i - 1] , g[i]) ;
if(i > 0) h[k] = max(h[k] , wg[i - 1] + g[i] );
else h[k] = max(h[k] , g[i]) ;
}
for(int i = 0;i < n ;i++) {
prepf[i] = p[i] * f[i] ;
if(i > 0) prepf[i] += prepf[i - 1];
// printf("i %d %lf %lf\n",i,f[i],p[i]) ;
}
sufp[n] =0;
for(int i = n - 1;i >= 0;i--) {
sufp[i] = sufp[i + 1] + p[i] ;
}
for(int i = 0;i < n;i++) f[i] = -f[i] ;
for(int i = k - 1;i >= 1;i--) {
int pos = (lower_bound(f + 0 , f + n , -h[i + 1]) - f) ;
// printf("POS %d\n",pos) ;
h[i] = sufp[pos ] * h[i + 1] ;
if(pos > 0) h[i] += prepf[pos - 1] ;
}
double ans = h[1] ;
printf("%.12lf\n" , ans) ;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 39ms
memory: 116728kb
input:
3 1 0.5 0.25 0.25 0.75 0.25 0.0 0.0
output:
0.687500000000
result:
ok found '0.6875000', expected '0.6875000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 40ms
memory: 116812kb
input:
3 2 0.3 0.4 0.3 0.0 0.0 0.0 1.0
output:
0.090000000000
result:
ok found '0.0900000', expected '0.0900000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 38ms
memory: 116828kb
input:
3 1 0.5 0.2 0.3 1.0 0.0 0.0 0.0
output:
0.800000000000
result:
ok found '0.8000000', expected '0.8000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 43ms
memory: 116656kb
input:
2 1 1.0 0.0 0.7 0.3
output:
0.700000000000
result:
ok found '0.7000000', expected '0.7000000', error '0.0000000'
Test #5:
score: 0
Accepted
time: 41ms
memory: 116784kb
input:
2 2 0.0 1.0 0.6 0.4
output:
0.600000000000
result:
ok found '0.6000000', expected '0.6000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 41ms
memory: 116716kb
input:
3 1 0.1 0.1 0.8 1.0 0.0 0.0 0.0
output:
0.900000000000
result:
ok found '0.9000000', expected '0.9000000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 36ms
memory: 116688kb
input:
2 1 0.196570 0.803430 0.417660 0.582340
output:
0.335560573800
result:
ok found '0.3355606', expected '0.3355606', error '0.0000000'
Test #8:
score: 0
Accepted
time: 38ms
memory: 116744kb
input:
2 1 0.392496 0.607504 1.000000 0.000000
output:
0.607504000000
result:
ok found '0.6075040', expected '0.6075040', error '0.0000000'
Test #9:
score: 0
Accepted
time: 36ms
memory: 116784kb
input:
10 1 0.012643 0.123624 0.053820 0.040365 0.028873 0.020157 0.055711 0.484945 0.098421 0.081441 0.085328 0.047990 0.714931 0.138813 0.012938 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
output:
0.901027547899
result:
ok found '0.9010275', expected '0.9010275', error '0.0000000'
Test #10:
score: 0
Accepted
time: 45ms
memory: 116744kb
input:
10 1 0.006649 0.073200 0.000565 0.045068 0.112668 0.035625 0.046072 0.103194 0.005569 0.571390 0.195573 0.074055 0.047683 0.369439 0.161507 0.054811 0.055588 0.037380 0.003964 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
output:
0.853833380837
result:
ok found '0.8538334', expected '0.8538334', error '0.0000000'
Test #11:
score: 0
Accepted
time: 42ms
memory: 116824kb
input:
10 1 0.145228 0.019318 0.105821 0.185187 0.088991 0.042625 0.024569 0.088478 0.047174 0.252609 0.018498 0.107130 0.001316 0.120833 0.069263 0.099338 0.005632 0.009075 0.036279 0.023135 0.008573 0.029578 0.025695 0.067194 0.023536 0.116172 0.157449 0.081304
output:
0.306330006553
result:
ok found '0.3063300', expected '0.3063300', error '0.0000000'
Test #12:
score: 0
Accepted
time: 45ms
memory: 116764kb
input:
10 10 0.044299 0.160436 0.044139 0.088241 0.291281 0.136777 0.020766 0.124310 0.013255 0.076496 0.081824 0.025457 0.068874 0.265701 0.558144 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
output:
0.999983853959
result:
ok found '0.9999839', expected '0.9999839', error '0.0000000'
Test #13:
score: 0
Accepted
time: 39ms
memory: 116776kb
input:
10 10 0.098756 0.001607 0.002767 0.264946 0.282086 0.080842 0.027809 0.031328 0.176685 0.033174 0.072398 0.177002 0.005668 0.017867 0.488488 0.060093 0.085645 0.025416 0.067423 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
output:
0.986428786179
result:
ok found '0.9864288', expected '0.9864288', error '0.0000000'
Test #14:
score: 0
Accepted
time: 41ms
memory: 116784kb
input:
10 10 0.429937 0.091639 0.001306 0.006129 0.006155 0.171890 0.227093 0.040566 0.003681 0.021604 0.041201 0.062705 0.028561 0.106362 0.004036 0.034025 0.097426 0.071704 0.050975 0.005562 0.042348 0.065488 0.055791 0.033996 0.101538 0.032639 0.105819 0.059824
output:
0.628303052313
result:
ok found '0.6283031', expected '0.6283031', error '0.0000000'
Test #15:
score: 0
Accepted
time: 42ms
memory: 116688kb
input:
1000 1000 0.000186 0.000277 0.000747 0.004770 0.001251 0.001097 0.001523 0.000697 0.002943 0.000903 0.000046 0.000063 0.000033 0.000233 0.000333 0.000385 0.000192 0.001261 0.002266 0.000046 0.001039 0.001668 0.000955 0.002996 0.000001 0.000635 0.001404 0.000237 0.000757 0.000273 0.001566 0.000076 0....
output:
1.000000000001
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #16:
score: 0
Accepted
time: 43ms
memory: 118764kb
input:
1000 1000 0.000547 0.000752 0.000703 0.001254 0.003381 0.000643 0.002170 0.000597 0.001286 0.005326 0.000228 0.000866 0.002296 0.000276 0.001162 0.000225 0.001080 0.002429 0.001119 0.001858 0.001548 0.000080 0.002263 0.000292 0.000358 0.000841 0.000658 0.001286 0.002226 0.004054 0.000382 0.001406 0....
output:
0.999998043069
result:
ok found '0.9999980', expected '0.9999980', error '0.0000000'
Test #17:
score: 0
Accepted
time: 43ms
memory: 116792kb
input:
1000 1000 0.000362 0.001464 0.000148 0.000631 0.000095 0.000870 0.000089 0.000110 0.000545 0.000621 0.001660 0.000251 0.000261 0.001025 0.001456 0.002287 0.000990 0.001421 0.000920 0.001709 0.002256 0.002731 0.000697 0.002399 0.003296 0.000171 0.000584 0.000437 0.001456 0.000772 0.000126 0.000171 0....
output:
0.758192052457
result:
ok found '0.7581921', expected '0.7581921', error '0.0000000'
Test #18:
score: 0
Accepted
time: 41ms
memory: 118832kb
input:
2 300000 0.044919 0.955081 1.000000 0.000000
output:
1.000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #19:
score: 0
Accepted
time: 48ms
memory: 118728kb
input:
2 300000 0.922991 0.077009 0.216415 0.783585
output:
0.276758097265
result:
ok found '0.2767581', expected '0.2767581', error '0.0000000'
Test #20:
score: 0
Accepted
time: 839ms
memory: 136412kb
input:
300000 1 0.000003 0.000000 0.000001 0.000003 0.000006 0.000001 0.000001 0.000001 0.000003 0.000003 0.000001 0.000003 0.000000 0.000005 0.000002 0.000001 0.000001 0.000002 0.000003 0.000002 0.000007 0.000000 0.000010 0.000000 0.000001 0.000000 0.000005 0.000009 0.000001 0.000002 0.000001 0.000006 0.0...
output:
0.500640852638
result:
ok found '0.5006409', expected '0.5006409', error '0.0000000'
Test #21:
score: 0
Accepted
time: 837ms
memory: 136408kb
input:
300000 1 0.000007 0.000000 0.000003 0.000020 0.000001 0.000001 0.000000 0.000009 0.000000 0.000004 0.000000 0.000002 0.000001 0.000001 0.000002 0.000012 0.000001 0.000004 0.000001 0.000004 0.000003 0.000005 0.000013 0.000001 0.000002 0.000007 0.000001 0.000001 0.000005 0.000003 0.000001 0.000002 0.0...
output:
0.250560883052
result:
ok found '0.2505609', expected '0.2505609', error '0.0000000'
Test #22:
score: 0
Accepted
time: 846ms
memory: 136352kb
input:
300000 10 0.000001 0.000001 0.000000 0.000000 0.000000 0.000001 0.000004 0.000001 0.000007 0.000004 0.000003 0.000002 0.000000 0.000004 0.000002 0.000001 0.000020 0.000001 0.000000 0.000003 0.000010 0.000001 0.000002 0.000013 0.000001 0.000007 0.000003 0.000006 0.000001 0.000001 0.000003 0.000001 0....
output:
0.979810412917
result:
ok found '0.9798104', expected '0.9798104', error '0.0000000'
Test #23:
score: 0
Accepted
time: 838ms
memory: 136456kb
input:
300000 10 0.000002 0.000002 0.000000 0.000001 0.000001 0.000001 0.000001 0.000014 0.000000 0.000004 0.000001 0.000002 0.000006 0.000000 0.000002 0.000002 0.000005 0.000001 0.000000 0.000001 0.000000 0.000003 0.000000 0.000001 0.000002 0.000000 0.000007 0.000000 0.000003 0.000002 0.000001 0.000003 0....
output:
0.675031975311
result:
ok found '0.6750320', expected '0.6750320', error '0.0000000'
Test #24:
score: 0
Accepted
time: 838ms
memory: 136384kb
input:
300000 100 0.000000 0.000002 0.000003 0.000007 0.000001 0.000004 0.000003 0.000000 0.000001 0.000000 0.000003 0.000001 0.000002 0.000000 0.000008 0.000002 0.000003 0.000002 0.000000 0.000004 0.000005 0.000004 0.000003 0.000004 0.000003 0.000001 0.000000 0.000005 0.000005 0.000003 0.000006 0.000002 0...
output:
0.999617530720
result:
ok found '0.9996175', expected '0.9996175', error '0.0000000'
Test #25:
score: 0
Accepted
time: 850ms
memory: 134400kb
input:
300000 100 0.000000 0.000006 0.000000 0.000001 0.000001 0.000003 0.000005 0.000005 0.000004 0.000000 0.000004 0.000001 0.000001 0.000000 0.000002 0.000001 0.000001 0.000001 0.000003 0.000007 0.000004 0.000000 0.000002 0.000002 0.000003 0.000002 0.000012 0.000003 0.000001 0.000002 0.000003 0.000000 0...
output:
0.740882930870
result:
ok found '0.7408829', expected '0.7408829', error '0.0000000'
Test #26:
score: 0
Accepted
time: 844ms
memory: 136440kb
input:
300000 300000 0.000000 0.000007 0.000002 0.000003 0.000003 0.000004 0.000006 0.000008 0.000002 0.000001 0.000002 0.000001 0.000000 0.000005 0.000012 0.000003 0.000000 0.000014 0.000000 0.000000 0.000003 0.000008 0.000001 0.000001 0.000002 0.000001 0.000001 0.000005 0.000005 0.000000 0.000003 0.00000...
output:
0.999999986178
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #27:
score: 0
Accepted
time: 844ms
memory: 136416kb
input:
300000 300000 0.000001 0.000003 0.000001 0.000005 0.000003 0.000001 0.000000 0.000002 0.000003 0.000002 0.000002 0.000001 0.000020 0.000002 0.000006 0.000008 0.000002 0.000003 0.000012 0.000002 0.000002 0.000001 0.000005 0.000001 0.000001 0.000008 0.000004 0.000000 0.000004 0.000002 0.000006 0.00001...
output:
0.750543568657
result:
ok found '0.7505436', expected '0.7505436', error '0.0000000'