結果
問題 | No.210 探し物はどこですか? |
ユーザー |
![]() |
提出日時 | 2015-05-26 23:10:30 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 2,152 bytes |
コンパイル時間 | 1,138 ms |
コンパイル使用メモリ | 162,052 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-06 10:19:49 |
合計ジャッジ時間 | 3,178 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define REP(i,a,b) for(i=a;i<b;i++) #define rep(i,n) REP(i,0,n) #define mygc(c) (c)=getchar_unlocked() #define mypc(c) putchar_unlocked(c) void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);} void writer(double x, char c){printf("%.15f",x);mypc(c);} template<class T> void writerLn(T x){writer(x,'\n');} template <class T> struct heapEx { int *hp, *place, size; T *val; void malloc(int N){hp=(int*)std::malloc(N*sizeof(int));place=(int*)std::malloc(N*sizeof(int));val=(T*)std::malloc(N*sizeof(T));} void free(){free(hp);free(place);free(val);} void* malloc(int N, void *workMemory){hp=(int*)workMemory;workMemory=(void*)(hp+N);place=(int*)workMemory;workMemory=(void*)(place+N);val=(T*)workMemory;workMemory=(void*)(val+N);return workMemory;} void init(int N){int i;size=0;rep(i,N)place[i]=-1;} void up(int n){int m;while(n){m=(n-1)/2;if(val[hp[m]]<=val[hp[n]])break;swap(hp[m],hp[n]);swap(place[hp[m]],place[hp[n]]);n=m;}} void down(int n){int m;for(;;){m=2*n+1;if(m>=size)break;if(m+1<size&&val[hp[m]]>val[hp[m+1]])m++;if(val[hp[m]]>=val[hp[n]])break;swap(hp[m],hp[n]);swap(place[hp[m]],place[hp[n]]);n=m;}} void change(int n, T v){T f=val[n];val[n]=v;if(place[n]==-1){place[n] = size;hp[size++] = n;up(place[n]);}else{if(f < v) down(place[n]); else if(f > v) up(place[n]);}} int pop(void){int res=hp[0];place[res]=-1;size--;if(size)hp[0]=hp[size],place[hp[0]]=0,down(0);return res;} }; int N, P[2000], Q[2000]; double p[2000], q[2000]; int main(){ int i, j, k, loop; double res = 0, pp = 1; heapEx<double> hp; reader(&N); rep(i,N) reader(P+i); rep(i,N) reader(Q+i); rep(i,N) p[i] = P[i] / 1000.0; rep(i,N) q[i] = Q[i] / 100.0; hp.malloc(N); hp.init(N); rep(i,N) hp.change(i, -p[i]*q[i]); rep(loop,400000){ i = hp.hp[0]; res -= (loop+1) * hp.val[i]; p[i] += hp.val[i]; pp += hp.val[i]; hp.change(i, -p[i]*q[i]); } res += (400000 + res/(1-pp) + pp*(50000+res)) * pp; writerLn(res); return 0; }