#include "iostream" #include "climits" #include "list" #include "queue" #include "stack" #include "set" #include "functional" #include "algorithm" #include "string" #include "map" #include "unordered_map" #include "unordered_set" #include "iomanip" #include "cmath" #include "random" #include "bitset" #include "cstdio" #include "numeric" #include "cassert" #include "ctime" using namespace std; using ll=long long int; //using Int=__int128; #define ALL(A) A.begin(),A.end() template bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;} template bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;} template constexpr int bitUP(T x,int a){return (x>>a)&1;} //→ ↓ ← ↑ int dh[4]={0,1,0,-1}, dw[4]={1,0,-1,0}; //右上から時計回り //int dh[8]={-1,0,1,1,1,0,-1,-1}, dw[8]={1,1,1,0,-1,-1,-1,0}; long double EPS = 1e-6; long double PI = acos(-1); const ll INF=(1LL<<62); const int MAX=(1<<30); constexpr ll MOD=1000000000+7; //constexpr ll MOD=998244353; inline void bin101(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20); } using pii=pair; using pil=pair; using pli=pair; using pll=pair; using psi=pair; using pis=pair; using psl=pair; using pls=pair; using pss=pair; using Graph=vector>; template struct edge { int to; T cost; edge()=default; edge(int to, T cost) : to(to), cost(cost) {} }; template using WeightGraph=vector>>; template void CinGraph(int M,WeightGraph &g,bool directed=false,bool index1=true){ while(M--){ int s,t; T cost; cin>>s>>t>>cost; if(index1) s--,t--; g[s].emplace_back(t,cost); if(not directed) g[t].emplace_back(s,cost); } } void CinGraph(int M,Graph &g,bool directed=false,bool index1=true){ while(M--){ int s,t; cin>>s>>t; if(index1) s--,t--; g[s].push_back(t); if(not directed) g[t].push_back(s); } } //0-indexed vector cin template inline istream &operator>>(istream &is,vector &v) { for(size_t i=0;i>v[i]; return is; } //0-indexed vector cin template inline istream &operator>>(istream &is,vector> &v) { for(size_t i=0;i>v[i]; } return is; } //vector cout template inline ostream &operator<<(ostream &os,const vector &v) { bool sp=true; if(string(typeid(T).name())=="c") sp=false; for(size_t i=0;i cout template inline ostream &operator<<(ostream &os,const vector> &v) { for(size_t i=0;i inline ostream &operator<<(ostream &os,const Graph &g) { for(size_t i=0;i"< inline ostream &operator<<(ostream &os,const WeightGraph &g) { for(size_t i=0;i"< inline vector vmake(size_t n,T x){ return vector(n,x); } //a,b,c,x data[a][b][c] 初期値x template auto vmake(size_t n,Args... args){ auto v=vmake(args...); return vector(n,move(v)); } template void fill(V &v,const T value){ v=value; } template void fill(vector &vec,const T value){ for(auto &v:vec) fill(v,value); } //pair cout template inline ostream &operator<<(ostream &os,const pair &p) { os< inline istream &operator>>(istream &is,pair &p) { is>>p.first>>p.second; return is; } //ソート template inline void vsort(vector &v){ sort(v.begin(),v.end()); } //逆順ソート template inline void rvsort(vector &v){ sort(v.rbegin(),v.rend()); } //1ビットの数を返す inline int popcount(int x){ return __builtin_popcount(x); } //1ビットの数を返す inline int popcount(ll x){ return __builtin_popcountll(x); } template inline void Compress(vector &C){ sort(C.begin(),C.end()); C.erase(unique(C.begin(),C.end()),C.end()); } template inline int lower_idx(const vector &C,T value){ return lower_bound(C.begin(),C.end(),value)-C.begin(); } template inline int upper_idx(const vector &C,T value){ return upper_bound(C.begin(),C.end(),value)-C.begin(); } //時計回りに90度回転 template inline void rotate90(vector> &C){ vector> D(C[0].size(),vector(C.size())); for(int h=0;h=H or w>=W or h<0 or w<0); } void NO(){ cout<<"NO"<<"\n"; } void YES(){ cout<<"YES"<<"\n"; } void No(){ cout<<"No"<<"\n"; } void Yes(){ cout<<"Yes"<<"\n"; } namespace overflow{ template T max(){ return numeric_limits::max(); } template T ADD(T a,T b){ T res; return __builtin_add_overflow(a,b,&res)?max():res; } template T MUL(T a,T b){ T res; return __builtin_mul_overflow(a,b,&res)?max():res; } }; using namespace overflow; struct mint{ using u64=uint_fast64_t; u64 a; constexpr mint() :a(0){} constexpr mint(ll x) :a((x>=0)?(x%MOD):(x%MOD+MOD) ) {} inline constexpr mint operator+(const mint rhs)const noexcept{ return mint(*this)+=rhs; } inline constexpr mint operator-(const mint rhs)const noexcept{ return mint(*this)-=rhs; } inline constexpr mint operator*(const mint rhs)const noexcept{ return mint(*this)*=rhs; } inline constexpr mint operator/(const mint rhs)const noexcept{ return mint(*this)/=rhs; } inline constexpr mint operator+(const ll rhs) const noexcept{ return mint(*this)+=mint(rhs); } inline constexpr mint operator-(const ll rhs)const noexcept{ return mint(*this)-=mint(rhs); } inline constexpr mint operator*(const ll rhs)const noexcept{ return mint(*this)*=mint(rhs); } inline constexpr mint operator/(const ll rhs)const noexcept{ return mint(*this)/=mint(rhs); } inline constexpr mint &operator+=(const mint rhs)noexcept{ a+=rhs.a; if(a>=MOD) a-=MOD; return *this; } inline constexpr mint &operator-=(const mint rhs)noexcept{ if(rhs.a>a) a+=MOD; a-=rhs.a; return *this; } inline constexpr mint &operator*=(const mint rhs)noexcept{ a=(a*rhs.a)%MOD; return *this; } inline constexpr mint &operator/=(mint rhs)noexcept{ a=(a*rhs.inverse().a)%MOD; return *this; } inline constexpr mint &operator+=(const ll rhs)noexcept{ return *this+=mint(rhs); } inline constexpr mint &operator-=(const ll rhs)noexcept{ return *this-=mint(rhs); } inline constexpr mint &operator*=(const ll rhs)noexcept{ return *this*=mint(rhs); } inline constexpr mint &operator/=(const ll rhs)noexcept{ return *this/=mint(rhs); } inline constexpr mint operator=(const ll x)noexcept{ a=(x>=0)?(x%MOD):(x%MOD+MOD); return *this; } inline constexpr bool operator==(const mint p)const noexcept{ return a==p.a; } inline constexpr bool operator!=(const mint p)const noexcept{ return a!=p.a; } inline constexpr mint pow(ll N) const noexcept{ mint ans(1LL),p(a); while(N>0){ if(bitUP(N,0)){ ans*=p; } p*=p; N>>=1; } return ans; } inline constexpr mint inverse() const noexcept{ return pow(MOD-2); } }; inline constexpr mint operator+(const ll &a,const mint &b)noexcept{ return mint(a)+=b; } inline constexpr mint operator-(const ll &a,const mint &b)noexcept{ return mint(a)-=b; } inline constexpr mint operator*(const ll &a,const mint &b)noexcept{ return mint(a)*=b; } inline constexpr mint operator/(const ll &a,const mint &b)noexcept{ return mint(a)/=b; } //cout inline ostream &operator<<(ostream &os,const mint &p) { return os<>(istream &is,mint &p) { ll t; is>>t; p=t; return is; } struct Binominal{ vector fac,finv,inv; //fac[n]:n! finv:(n!)の逆元 int sz; Binominal(int n=10) :sz(1){ if(n<=0) n=10; init(n); } inline void init(int n){ fac.resize(n+1,1); finv.resize(n+1,1); inv.resize(n+1,1); for(int i=sz+1;i<=n;i++){ fac[i]=fac[i-1]*i; inv[i]=MOD-inv[MOD%i]*(MOD/i); finv[i]=finv[i-1]*inv[i]; } sz=n; } //nCk(n,k<=N) をO(1)で求める inline mint com(int n,int k){ if(nsz) init(n); return fac[n]*finv[k]*finv[n-k]; } //nCk(k<=N) をO(k) で求める inline mint rcom(ll n,int k){ if(n<0 || k<0 || nsz) init(k); mint ret(1); for(int i=0;isz) init(n); return fac[n]*finv[n-k]; } }; vector Subset(int S,bool zero=false,bool full=false){ vector ret; int now=(S-1)&S; if(full and S){ ret.push_back(S); } do{ ret.push_back(now); now=(now-1)&S; }while(now!=0); if(zero){ ret.push_back(0); } return ret; } template T SUM(const vector &v,int s,int t){ chmax(s,0); chmin(t,int(v.size())-1); if(s>t) return 0; if(s==0) return v[t]; else return v[t]-v[s-1]; } template void buildSUM(vector &v){ for(size_t i=1;i struct BIT{ vector data; BIT(int sz){ data.assign(sz+2,0); } // [0,k]の合計 T sum(int k){ T ans=0; k++; while(k>0){ ans+=data[k]; k-=k&(-k); } return ans; } // data[r:l]の合計 T sum(int r,int l){ return sum(l)-sum(r-1); } void add(int k,T x){ k++; while(k>N; vector A(N),B(N); cin>>A>>B; using DD=long double; vector
opt_x(N),opt(N); for(int i=0;if(mid_high,a,b)) low=mid_low; //ダメな方を更新 else high=mid_high; } opt_x[i]=low; opt[i]=f(low,A[i],B[i]); } vector order(N); vector order_id(N); for(int i=0;i sumO(N),sumA(N),sumB(N); for(int i=0;i=0){ DD O=sumO.sum(id); DD A=sumA.sum(id); DD B=sumB.sum(id); ret+=f(a,A,B); ret-=O; } return ret; }; //cerr<g(mid_high)) low=mid_low; //ダメな方を更新 else high=mid_high; } x=low; ans+=f(low,A[i],B[i]); } cout<>T; while(T--) solve(); }