QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#200351 | #7344. Those Russian Hackers | Delay_for_five_minutes# | WA | 49ms | 116784kb | C++20 | 3.4kb | 2023-10-04 16:36:12 | 2023-10-04 16:36:13 |
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;
}
详细
Test #1:
score: 100
Accepted
time: 30ms
memory: 116744kb
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: 116744kb
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: 49ms
memory: 116784kb
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: 36ms
memory: 116752kb
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: 35ms
memory: 116728kb
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: -100
Wrong Answer
time: 36ms
memory: 116688kb
input:
3 1 0.1 0.1 0.8 1.0 0.0 0.0 0.0
output:
1.700000000000
result:
wrong answer 1st numbers differ - expected: '0.9000000', found: '1.7000000', error = '0.8000000'