結果
| 問題 | No.3604 Min of Max of Div of Sum |
| コンテスト | |
| ユーザー |
 Taiki0715
|
| 提出日時 | 2026-07-31 21:43:18 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 1,530 ms / 2,000 ms |
| + 502µs | |
| コード長 | 15,981 bytes |
| 記録 | |
| コンパイル時間 | 2,208 ms |
| コンパイル使用メモリ | 342,484 KB |
| 実行使用メモリ | 11,224 KB |
| 最終ジャッジ日時 | 2026-07-31 21:43:36 |
| 合計ジャッジ時間 | 17,405 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using P=pair<ll,ll>;
template<typename T>using minque=priority_queue<T,vector<T>,greater<T>>;
template<typename T>bool chmax(T &a,const T &b){return (a<b?(a=b,true):false);}
template<typename T>bool chmin(T &a,const T &b){return (a>b?(a=b,true):false);}
template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}
template<typename T1,typename T2,typename T3>istream &operator>>(istream &is,tuple<T1,T2,T3>&a){is>>std::get<0>(a)>>std::get<1>(a)>>std::get<2>(a);return is;}
template<typename T,size_t n>istream &operator>>(istream &is,array<T,n>&a){for(auto&i:a)is>>i;return is;}
template<typename T>istream &operator>>(istream &is,vector<T> &a){for(auto &i:a)is>>i;return is;}
template<typename T1,typename T2>void operator++(pair<T1,T2>&a,int n){a.first++,a.second++;}
template<typename T1,typename T2>void operator--(pair<T1,T2>&a,int n){a.first--,a.second--;}
template<typename T>void operator++(vector<T>&a,int n){for(auto &i:a)i++;}
template<typename T>void operator--(vector<T>&a,int n){for(auto &i:a)i--;}
#define overload3(_1,_2,_3,name,...) name
#define rep1(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define rep(...) overload3(__VA_ARGS__,rep2,rep1)(__VA_ARGS__)
#define reps(i,l,r) rep2(i,l,r)
#define all(x) x.begin(),x.end()
#define pcnt(x) __builtin_popcountll(x)
#define fin(x) return cout<<(x)<<'\n',static_cast<void>(0)
#define yn(x) cout<<((x)?"Yes\n":"No\n")
#define uniq(x) sort(all(x)),x.erase(unique(all(x)),x.end())
template<typename T>
inline int fkey(vector<T>&z,T key){return lower_bound(z.begin(),z.end(),key)-z.begin();}
ll myceil(ll a,ll b){return (a+b-1)/b;}
template<typename T,size_t n,size_t id=0>
auto vec(const int (&d)[n],const T &init=T()){
if constexpr (id<n)return vector(d[id],vec<T,n,id+1>(d,init));
else return init;
}
#ifdef LOCAL
#include<debug.h>
#define SWITCH(a,b) (a)
#else
#define debug(...) static_cast<void>(0)
#define debugg(...) static_cast<void>(0)
#define SWITCH(a,b) (b)
template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<' '<<p.second;return os;}
#endif
struct Timer{
clock_t start;
Timer(){
start=clock();
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout<<fixed<<setprecision(16);
}
inline double now(){return (double)(clock()-start)/1000;}
#ifdef LOCAL
~Timer(){
cerr<<"time:";
cerr<<now();
cerr<<"ms\n";
}
#endif
}timer;
void SOLVE();
int main(){
int testcase=1;
//cin>>testcase;
for(int i=0;i<testcase;i++){
SOLVE();
}
}
#include<type_traits>
template<typename T,std::enable_if_t<std::is_integral_v<T>,std::nullptr_t> =nullptr,typename Func>
T bin_search(T ok,T ng,const Func&f){
while(std::abs(ok-ng)>1){
T mid=(ok&ng)+((ok^ng)>>1);
(f(mid)?ok:ng)=mid;
}
return ok;
}
template<typename T,std::enable_if_t<std::is_floating_point_v<T>,int> loop=100,typename Func>
T bin_search(T ok,T ng,const Func&f){
for(int i=0;i<loop;i++){
T mid=(ok+ng)/2;
(f(mid)?ok:ng)=mid;
}
return ok;
}
#include<concepts>
struct has_update_impl{
template<typename T>
static auto check(T&&x)->decltype(x.update(),std::true_type{});
template<typename T>
static auto check(...)->std::false_type;
};
template<typename T>
struct has_update:public decltype(has_update_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_update_v=has_update<T>::value;
struct has_push_impl{
template<typename T>
static auto check(T&&x)->decltype(x.push(),std::true_type{});
template<typename T>
static auto check(...)->std::false_type;
};
template<typename T>
struct has_push:public decltype(has_push_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_push_v=has_push<T>::value;
struct has_middle_impl{
template<typename T>
static auto check(T&&x)->decltype(x.middle,std::true_type{});
template<typename T>
static auto check(...)->std::false_type;
};
template<typename T>
struct has_middle:public decltype(has_middle_impl::check<T>(std::declval<T>())){};
template<typename T>
inline constexpr bool has_middle_v=has_middle<T>::value;
template<typename T>
concept can_copy_monoid=requires(T x){
x.copy_monoid(std::declval<T*>());
};
template<typename T,bool no_push=false>
void splay(T*nd){
if constexpr(has_push_v<T>&&!no_push)nd->push();
while(nd->par){
T *p=nd->par;
T *pp=p->par;
if constexpr(has_push_v<T>&&!no_push){
if(pp)pp->push();
p->push();
nd->push();
}
if(p->left==nd){
if(pp){
if(pp->left==p){
nd->par=pp->par;
if(pp->par){
if constexpr(has_middle_v<T>){
if(pp->par->middle==pp)nd->par->middle=nd;
else if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
else{
if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
}
pp->left=p->right;
if(pp->left)pp->left->par=pp;
p->left=nd->right;
if(p->left)p->left->par=p;
nd->right=p;
p->par=nd;
p->right=pp;
pp->par=p;
if constexpr(has_update_v<T>){
if constexpr(can_copy_monoid<T>)nd->copy_monoid(pp),pp->update(),p->update();
else pp->update(),p->update(),nd->update();
}
continue;
}
else if(pp->right==p){
nd->par=pp->par;
if(pp->par){
if constexpr(has_middle_v<T>){
if(pp->par->middle==pp)nd->par->middle=nd;
else if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
else{
if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
}
p->left=nd->right;
if(p->left)p->left->par=p;
pp->right=nd->left;
if(pp->right)pp->right->par=pp;
nd->left=pp;
pp->par=nd;
nd->right=p;
p->par=nd;
if constexpr(has_update_v<T>){
if constexpr(can_copy_monoid<T>)nd->copy_monoid(pp),pp->update(),p->update();
else pp->update(),p->update(),nd->update();
}
continue;
}
}
nd->par=pp;
if(pp){
if constexpr(has_middle_v<T>){
if(pp->middle==p)pp->middle=nd;
else if(pp->left==p)pp->left=nd;
else if(pp->right==p)pp->right=nd;
}
else{
if(pp->left==p)pp->left=nd;
else if(pp->right==p)pp->right=nd;
}
}
p->left=nd->right;
if(p->left)p->left->par=p;
nd->right=p;
p->par=nd;
if constexpr(has_update_v<T>){
if constexpr(can_copy_monoid<T>)nd->copy_monoid(p),p->update();
else p->update(),nd->update();
}
break;
}
else if(p->right==nd){
if(pp){
if(pp->left==p){
nd->par=pp->par;
if(pp->par){
if constexpr(has_middle_v<T>){
if(pp->par->middle==pp)nd->par->middle=nd;
else if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
else{
if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
}
p->right=nd->left;
if(p->right)p->right->par=p;
pp->left=nd->right;
if(pp->left)pp->left->par=pp;
nd->left=p;
p->par=nd;
nd->right=pp;
pp->par=nd;
if constexpr(has_update_v<T>){
if constexpr(can_copy_monoid<T>)nd->copy_monoid(pp),pp->update(),p->update();
else pp->update(),p->update(),nd->update();
}
continue;
}
else if(pp->right==p){
nd->par=pp->par;
if(pp->par){
if constexpr(has_middle_v<T>){
if(pp->par->middle==pp)nd->par->middle=nd;
else if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
else{
if(pp->par->left==pp)nd->par->left=nd;
else if(pp->par->right==pp)nd->par->right=nd;
}
}
pp->right=p->left;
if(pp->right)pp->right->par=pp;
p->right=nd->left;
if(p->right)p->right->par=p;
nd->left=p;
p->par=nd;
p->left=pp;
pp->par=p;
if constexpr(has_update_v<T>){
if constexpr(can_copy_monoid<T>)nd->copy_monoid(pp),pp->update(),p->update();
else pp->update(),p->update(),nd->update();
}
continue;
}
}
nd->par=pp;
if(pp){
if constexpr(has_middle_v<T>){
if(pp->middle==p)pp->middle=nd;
else if(pp->left==p)pp->left=nd;
else if(pp->right==p)pp->right=nd;
}
else{
if(pp->left==p)pp->left=nd;
else if(pp->right==p)pp->right=nd;
}
}
p->right=nd->left;
if(p->right)p->right->par=p;
nd->left=p;
p->par=nd;
if constexpr(has_update_v<T>){
if constexpr(can_copy_monoid<T>)nd->copy_monoid(p),p->update();
else p->update(),nd->update();
}
break;
}
else break;
}
}
template<typename T>
[[nodiscard]]T* near(T *nd,decltype(T::key)k){
while(true){
if(k<nd->key){
if constexpr(has_push_v<T>)nd->push();
if(nd->left)nd=nd->left;
else{
splay<T,true>(nd);
return nd;
}
}
else if(nd->key<k){
if constexpr(has_push_v<T>)nd->push();
if(nd->right)nd=nd->right;
else{
splay<T,true>(nd);
return nd;
}
}
else{
splay<T,true>(nd);
return nd;
}
}
return nullptr;
}
template<typename T>
[[nodiscard]]T* get_k(T *nd,decltype(T::sz)k){
while(true){
if constexpr(has_push_v<T>)nd->push();
decltype(T::sz) lsz=nd->left?nd->left->sz:0;
if(lsz==k)break;
else if(k<lsz)nd=nd->left;
else{
nd=nd->right;
k-=1+lsz;
}
}
splay<T,true>(nd);
return nd;
}
template<typename T>
[[nodiscard]]T* merge(T* l,T *r){
if(!l)return r;
if(!r)return l;
while(r->left){
if constexpr(has_push_v<T>)r->push();
r=r->left;
}
if constexpr(has_push_v<T>)r->push();
splay<T,true>(r);
r->left=l;
l->par=r;
if constexpr(has_update_v<T>)r->update();
return r;
}
template<typename T,bool correct_parent=true>
[[nodiscard]]T* left_most(T*nd){
T nil;
T *rnd=&nil;
while(nd->left){
if constexpr(has_push_v<T>)nd->push();
T *c=nd->left;
if(!c->left){
rnd->left=nd;
if constexpr(has_update_v<T>||correct_parent)nd->par=rnd;
rnd=rnd->left;
nd=c;
}
else{
if constexpr(has_push_v<T>)c->push();
nd->left=c->right;
c->right=nd;
if constexpr(has_update_v<T>||correct_parent){
if(nd->left)nd->left->par=nd;
nd->par=c;
}
if constexpr(has_update_v<T>)nd->update();
if constexpr(has_update_v<T>||correct_parent)c->par=rnd;
rnd->left=c;
nd=c->left;
rnd=rnd->left;
}
}
if constexpr(has_push_v<T>)nd->push();
rnd->left=nd->right;
nd->right=nil.left;
nil.left=nil.right=nullptr;
if constexpr(has_update_v<T>||correct_parent){
if(rnd->left)rnd->left->par=rnd;
if(nd->right)nd->right->par=nd;
nd->par=nullptr;
}
if constexpr(has_update_v<T>){
if(rnd!=&nil){
while(rnd){
rnd->update();
rnd=rnd->par;
}
}
}
return nd;
}
template<typename T,bool correct_parent=true>
[[nodiscard]]T* right_most(T*nd){
T nil;
T *lnd=&nil;
while(nd->right){
if constexpr(has_push_v<T>)nd->push();
T *c=nd->right;
if(!c->right){
lnd->right=nd;
if constexpr(has_update_v<T>||correct_parent)nd->par=lnd;
lnd=lnd->right;
nd=c;
}
else{
if constexpr(has_push_v<T>)c->push();
nd->right=c->left;
c->left=nd;
if constexpr(has_update_v<T>||correct_parent){
if(nd->right)nd->right->par=nd;
nd->par=c;
}
if constexpr(has_update_v<T>){
nd->update();
}
if constexpr(has_update_v<T>||correct_parent)c->par=lnd;
lnd->right=c;
nd=c->right;
lnd=lnd->right;
}
}
if constexpr(has_push_v<T>)nd->push();
lnd->right=nd->left;
nd->left=nil.right;
nil.left=nil.right=nullptr;
if constexpr(has_update_v<T>||correct_parent){
if(lnd->right)lnd->right->par=lnd;
if(nd->left)nd->left->par=nd;
nd->par=nullptr;
}
if constexpr(has_update_v<T>){
if(lnd!=&nil){
while(lnd){
lnd->update();
lnd=lnd->par;
}
}
}
return nd;
}
template<typename I,typename M>
struct DynamicSegmentTree{
private:
using S=typename M::S;
struct node{
node *left,*right,*par;
I key;
S v,sum;
node(I key,S v):left(nullptr),right(nullptr),par(nullptr),key(key),v(v),sum(v){}
void update(){
sum=v;
if(left)sum=M::op(left->sum,sum);
if(right)sum=M::op(sum,right->sum);
}
inline void copy_monoid(node *pp){sum=pp->sum;}
~node(){
if(left)delete left;
if(right)delete right;
}
};
node *root;
public:
DynamicSegmentTree():root(nullptr){}
void set(I key,S v){
if(!root){
root=new node(key,v);
return;
}
root=near(root,key);
if(root->key==key){
root->v=v;
root->update();
}
else{
node *nd=new node(key,v);
if(key<root->key){
nd->left=root->left;
if(nd->left)nd->left->par=nd;
root->left=nd;
nd->par=root;
}
else{
nd->right=root->right;
if(nd->right)nd->right->par=nd;
root->right=nd;
nd->par=root;
}
nd->update();
root->update();
}
}
S get(I key){
if(!root)return M::e();
root=near(root,key);
return root->key==key?root->v:M::e();
}
S prod(I l,I r){
assert(l<=r);
if(!root||l==r)return M::e();
root=near(root,l);
S res=M::e();
if(l<=root->key&&root->key<r)res=root->v;
if(root->right){
node *rnd=root->right;
rnd->par=nullptr;
rnd=near(rnd,r);
if(rnd->left)res=M::op(res,rnd->left->sum);
if(rnd->key<r)res=M::op(res,rnd->v);
root->right=rnd;
rnd->par=root;
}
return res;
}
S all_prod(){return root?root->sum:M::e();}
void deallocate(){
if(root)delete root;
}
};
template<typename T,T E=std::numeric_limits<T>::min()>
struct MonoidMax{
using S=T;
using F=std::nullptr_t;
static inline S op(const S&x,const S&y){return x<y?y:x;}
static inline S e(){return E;}
static inline S mapping(F,const S&x,long long){return x;}
static inline F composition(F,F){return nullptr;}
static inline F id(){return nullptr;}
static inline void revS(S&x){}
static inline S pow(const S&x,long long p){return x;}
};
void SOLVE(){
int n;
cin>>n;
vector<ll>a(n),b(n);
cin>>a>>b;
a.push_back(0);
b.push_back(0);
for(int i=n-1;i>=0;i--){
a[i]+=a[i+1];
b[i]+=b[i+1];
}
auto eval=[&](int l,int r)->double {
return (double)(a[l]-a[r])/(b[l]-b[r]);
};
auto f=[&](double x){
DynamicSegmentTree<double,MonoidMax<int>>seg;
vector<int>imos(n+1);
for(int i=n;i>=0;i--){
double now=a[i]-x*b[i];
int mx=seg.prod(-1e200,now);
if(i<mx){
imos[i]++;
imos[mx]--;
}
seg.set(now,max(seg.get(now),i));
}
rep(i,n)imos[i+1]+=imos[i];
seg.deallocate();
return any_of(all(imos)-1,[&](int v){return v==0;});
};
cout<<bin_search<double>(1e18,0,f)<<endl;
}