#include <bits/stdc++.h>
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#include <bits/extc++.h>
using namespace std;
#define int i64
#define FP_EPS 1e-11
#define COUT_FP 11
using f64=double; //long double(살짝느림),__float128(매우느림)
#define CPP20 1
#define ARGAUTO 1
#define DBG_SETW 3
//#define CONCEPT
#define pushb(...) push_back({__VA_ARGS__})
#define pushf(...) push_front({__VA_ARGS__})
#define push_(...) push({__VA_ARGS__})
#define popb pop_back
#define popf pop_front
#define fi first
#define se second
#define mkp make_pair
#define mkt make_tuple
#define cxp constexpr
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define reduce accumulate
#define itos to_string
using i64=long long;using u64=unsigned long long;
using pint=pair<int,int>;using tint=tuple<int,int,int>;
template<class T>using Str=basic_string<T>;
template<class T,class CMP=greater<>>using PQ=std::priority_queue<T,vector<T>,CMP>;
#define head(x) (x.begin())
#define tail(x) prev(x.end())
//Handy Funcs
template<class T>int sz(const T& x){return x.size();}
int divc(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?(a+b-1)/b:a/b;}
int divf(int a,int b){if(b<0)a=-a,b=-b;return (a>0)?a/b:(a-b+1)/b;}
cxp i64 lg2f(i64 x){return 63-__builtin_clzll(x);}
cxp i64 lg2c(i64 x){return 64-__builtin_clzll(x-1);}
template<class T>T sq(T x){return x*x;}
void WARN(bool cond,const char* str){
#if DEBUG
static set<const char*> z;
if(cond&&!z.count(str))z.insert(str),cerr<<"[WARN] "<<str<<endl;
#endif
}
template<class T>cxp T inf(){return numeric_limits<T>::max()/2;}
#ifdef CONCEPT
template<typename T> concept MemberInf=requires(T t){t.inf();};
template<MemberInf T>T inf(){return T().inf();}
#endif
template<class T, class P=vector<T>>
struct Arr:public P{
Arr(){P::shrink_to_fit();}
explicit Arr(signed n):P(n){}
explicit Arr(signed n,T init):P(n,init){}
Arr(initializer_list<T>il):P(il){}
#if ARGAUTO
Arr(auto its, auto ite):P(its,ite){}
#endif
inline T& operator[](signed i){
int n=sz(*this);
if(i<0)i+=n,WARN(1,"Neg Index Found");
if(i>=n)i-=n,WARN(1,"Over Index Found");
return P::operator[](i);
}
const T& operator[](signed i)const{
int n=sz(*this);
if(i<0)i+=n,WARN(1,"Neg Index Found");
if(i>=n)i-=n,WARN(1,"Over Index Found");
return P::operator[](i);
}
T& at(signed i){return *this[i];}
const T& at(signed i)const{return *this[i];}
};
#if ARGAUTO
template<class... A> auto ARR(auto n,A&&... a)
{if constexpr(!sizeof...(a)) return n; else return Arr(n,ARR(a...));}
#endif
#define ARG(...) __VA_ARGS__
#define func(RetT,fname,...) function<RetT(__VA_ARGS__)> fname=[&](__VA_ARGS__)->RetT
#define lam(expr,...) [&](__VA_ARGS__){return expr;}
#define lamp(expr,...) [](__VA_ARGS__){return expr;}
template<class T,class U>bool assmin(T& a,U&& b){return a>b?a=b,true:false;}
template<class T,class U>bool assmax(T& a,U&& b){return a<b?a=b,true:false;}
template<class T>int argmin(const Arr<T>& a){return min_element(a.begin(),a.end())-a.begin();}
template<class T>int argmax(const Arr<T>& a){return max_element(a.begin(),a.end())-a.begin();}
// Arr<int> range(int n){Arr<int> r;while(n--)r.pushb(sz(r));return r;} std::iota써라
template<class T>Arr<pair<int,T>> enumer(const Arr<T>& a){//views::enumerate in c++23
Arr<pair<int,T>> r;
for(auto&i:a)r.pushb(sz(r),i);
return r;
}
Arr<int> permuinv(const Arr<int>& a){
Arr<int> r(sz(a));
for(auto [i,v]:enumer(a))r[v]=i;
return r;
}
Arr<Arr<int>> occur(const Arr<int>& a){
Arr<Arr<int>> r(*max_element(a.begin(),a.end()));
for(auto [i,v]:enumer(a))r[v].pushb(i);
return r;
}
//Consts
// const f64 pi=numbers::pi_v<f64>,eps=FP_EPS;
const f64 pi=acos(-1),eps=FP_EPS;
const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
//Pre-runs
#if !(DEBUG)
auto __PR1=(ios::sync_with_stdio(0),cin.tie(0),cout.tie(0));
#endif
auto& __PR2=(cout<<fixed<<setprecision(COUT_FP));
//
#define FASTIO
//INPUT, strstream으로 더 깔끔하게 가능할까?
struct FastCIN{
static const int SZ=1<<24;
unsigned cnt=0;char a[SZ+1],*p;
FastCIN(){preload();}
void tie(int x){}
int preload(){return cnt=cin.read(p=a,SZ).gcount();}
inline char pop(){if(!cnt)preload(); return cnt>0?cnt--,*p++:0;}
inline char get(){if(!cnt)preload(); return cnt>0?*p:0;}
void ignore_wsc(){while(get()==' '||get()=='\n')pop();}
operator bool(){return get();}
template<class T>FastCIN& operator>>(T& n){ignore_wsc();n=0;char neg=false;if(get()=='-')neg=true,pop();while('0'<=get()&&get()<='9')n=n*10+pop()-'0';if(neg)n*=-1;return *this;}//int,i64,Mod<mod>
FastCIN& operator>>(char& c){ignore_wsc();c=pop();return *this;}
FastCIN& operator>>(string& s){ignore_wsc();s.clear();while(get()!=' '&&get()!='\n'&&get())s.pushb(pop());return *this;}
FastCIN& operator>>(f64& n){ignore_wsc();string s;while(('0'<=get()&&get()<='9')||get()=='.'||get()=='-')s.pushb(pop());n=stod(s);return *this;}
template<class T> FastCIN& operator>>(Arr<T>& a){for(auto& i:a)*this>>i;return *this;}
template<class T,class U> FastCIN& operator>>(pair<T,U>& a){*this>>a.fi>>a.se;return *this;}
}fcin;
#define cin fcin
template<class... A> void _cinread(A&...a){((cin>>(a)),...);}
#define READ(T,...) T __VA_ARGS__;_cinread(__VA_ARGS__);
template<class T> ostream& operator<<(ostream& s,const Arr<T>& a){for(auto i:a)cout<<i<<' ';return s;}
template<class T> ostream& operator<<(ostream& o,const pair<T,T>& x){return o<<x.fi<<' '<<x.se;}
template<class... A> void PRINT(A...a){((cout<<a<<' '),...,(cout<<endl));}
//
//TODO: concept로 인터페이스 추상화(서로 교점 하나인 그래프면 관리가능하다 함)시키고,cht.L과 lichao.LL도 geom.Line으로 통합시키자.
struct LL{
static LL id(){return {0,0.-inf<int>()};}
f64 a,b;
f64 f(f64 x){return a*x+b;}
};
//max lichao임. min필요하면 add(-a,-b),-q(x)
//TODO: 정수lichao추가.
//지금당장은 f64=longdouble, eps=1e-0, ans=round(f(x))로 쓰면 되긴함.
template<class T,int xlo=-inf<int>(),int xhi=inf<int>()>
struct LiChao{
T v=T::id();
LiChao *l{},*r{};
void add(T x,f64 cs=xlo,f64 ce=xhi){
if(ce-cs<eps)return;
f64 cm=(cs+ce)/2;
if(!l)l=new LiChao;
if(!r)r=new LiChao;
LL flo=v,fhi=x;//x=cs기준 직선의 lo,hi
if(fhi.f(cs)<flo.f(cs)) swap(flo,fhi);
if(flo.f(ce)<=fhi.f(ce)) v=fhi;
else if(flo.f(cm)<=fhi.f(cm)) v=fhi,r->add(flo,cm,ce);
else v=flo,l->add(fhi,cs,cm);
//NOTE: flo를 저장할땐 fhi를 넘기고, fhi를 저장할땐 flo를 넘기는건 나중에 쿼리할때 저장한거 외에 더 내려갈때 다른쪽꺼 체크되게 하기 위함인듯. 이부분이 제일 이해하기 tricky한 부분인거같다...
}
f64 q(f64 x,f64 cs=xlo,f64 ce=xhi){
f64 cm=(cs+ce)/2;
f64 ret=v.f(x);
if(x<cm and l)ret=max(ret,l->q(x,cs,cm));
if(x>=cm and r)ret=max(ret,r->q(x,cm,ce));
return ret;
}
};
//Don't use it at interactive
#define endl '\n'
void solve(){
int n,k; cin>>n>>k;
// auto dp=ARR(k+1,n+2,0.-inf<int>());
// dp[-1][0]=0;
// for(int x=0;x<k;x++){
// LiChao<LL> z;
// z.add({dp[x-1][0]+1,0.-0});
// for(int y=1;y<=n;y++){
// z.add({dp[x-1][y]+1,0.-y});
// dp[x][y]=z.q(y)/y;
// }
// }
// cout<<dp[k-1][n]<<endl;
// f64 s=0,e=n;
// while(e-s>1e-6){
// f64 m=(s+e)/2;
// //정확히 K번의 라운드 대신, 라운드당 람다(m)의 패널티를 부여해서 계산?
// //m=0이면 n번의 라운드 진행
// //m=n이면 1번의 라운드 진행
// //현재인원x라 할때 (반드시 전부다) 이겨서 얻는 점수 최대화
// //f(x) = max(y<x,f(y)+(x-y)/x-m) = max(y<x,(f(y)+1-m)x-y)/x
// //역추적으로 라운드개수 구해서 k와 비교. cht역추적...
// }
//그냥 삼분탐색으로 최솟값구해서 +mk하면 답이 된다는듯?
//최대화문제가 최소화 삼분탐색이 되는건 라그랑주듀얼 같은데 아직 헷갈린다.
func(f64,f,f64 m){
LiChao<LL> z;
z.add({-m,0});
f64 val;
for(int i=1;i<=n;i++){
val=z.q(i)/i;
z.add({val+1-m,0.-i});
}
return val+m*k;
};
f64 s=0,e=2;
while(e-s>1e-6){
f64 m1=(s*2+e)/3,m2=(s+e*2)/3;
// cout<<m1<<' '<<f(m1)<<' '<<m2<<' '<<f(m2)<<endl;
if(f(m1)>f(m2)) s=m1;
else e=m2;
}
cout<<f(s)+1<<endl;//1 작게나오는 이유 뭐지 ????
}
signed main(){
// int ti=0,t;cin>>t;
// while(++ti<=t)
// cout<<"Case #"<<ti<<": ",
solve();
}
Compilation message
akvizna.cpp:67:6: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
67 | Arr(auto its, auto ite):P(its,ite){}
| ^~~~
akvizna.cpp:67:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
67 | Arr(auto its, auto ite):P(its,ite){}
| ^~~~
akvizna.cpp:85:31: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
85 | template<class... A> auto ARR(auto n,A&&... a)
| ^~~~
akvizna.cpp: In static member function 'static _Res std::_Function_handler<_Res(_ArgTypes ...), _Functor>::_M_invoke(const std::_Any_data&, _ArgTypes&& ...) [with _Res = double; _Functor = solve()::<lambda(f64)>; _ArgTypes = {double}]':
akvizna.cpp:236:16: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
236 | return val+m*k;
| ^
akvizna.cpp:231:7: note: 'val' was declared here
231 | f64 val;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
820 KB |
Output is correct |
2 |
Correct |
3 ms |
696 KB |
Output is correct |
3 |
Correct |
3 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
832 KB |
Output is correct |
2 |
Correct |
3 ms |
808 KB |
Output is correct |
3 |
Correct |
3 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
844 KB |
Output is correct |
2 |
Correct |
3 ms |
972 KB |
Output is correct |
3 |
Correct |
4 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
716 KB |
Output is correct |
2 |
Correct |
7 ms |
992 KB |
Output is correct |
3 |
Correct |
3 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
116 ms |
17644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
127 ms |
18928 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
119 ms |
18552 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
133 ms |
18488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
116 ms |
18236 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
109 ms |
16668 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
129 ms |
19184 KB |
Output is correct |
2 |
Incorrect |
151 ms |
19452 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
113 ms |
17928 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
123 ms |
19192 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1584 ms |
212020 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1595 ms |
196396 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1596 ms |
220280 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1577 ms |
215380 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1593 ms |
215040 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1591 ms |
209744 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1593 ms |
212760 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1558 ms |
204220 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1596 ms |
183944 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1599 ms |
215512 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1594 ms |
220728 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1573 ms |
214348 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1581 ms |
207332 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |