QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#200369#7344. Those Russian HackersDelay_for_five_minutes#AC ✓850ms136456kbC++203.4kb2023-10-04 16:43:072023-10-04 16:43:07

Judging History

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

  • [2023-10-04 16:43:07]
  • 评测
  • 测评结果:AC
  • 用时:850ms
  • 内存:136456kb
  • [2023-10-04 16:43:07]
  • 提交

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'