Codeforces Round #584 - Dasha Code Championship - Elimination Round H問題 (4000pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, L;
int X, Y; double S;
double w[4d5], s[4d5], a[4d5];
int sz;
{
int i, k;
double gn, nd, y;
double res = 0;
LHeap<double> hp;
i = 0;
rd(N,L);
rep(N){
rd(X,Y,S);
if(i < X){
w[sz] = X - i;
s[sz++] = 0;
}
w[sz] = Y - X;
s[sz++] = S;
i = Y;
}
if(i < L){
w[sz] = L - i;
s[sz++] = 0;
}
rep(i,sz) a[i] = 1;
hp.walloc(sz);
hp.init(sz);
rep(k,sz){
while(hp.size){
i = hp.hp[0];
if(s[i] <= s[k]) break;
gn = w[i] / s[i] - w[i] / (s[i] + a[i]) * (1 - a[i]);
nd = w[k] / (s[k] + 2) + w[k] / (s[k] + a[k]) * (1 - a[k]);
if(nd < gn){
a[k] = 2;
y = w[i] / (s[i]+a[i]) * (1-a[i]) + nd;
a[i] = (w[i] - y * s[i]) / (w[i] + y);
break;
} else {
a[i] = 0;
y = w[k] / (s[k]+a[k]) * (1-a[k]) - gn;
a[k] = (w[k] - y * s[k]) / (w[k] + y);
hp.pop();
}
}
if(a[k]) hp.change(k, -s[k]);
}
rep(i,sz) res += w[i] / (s[i] + a[i]);
wt(res);
}
Current time: 2024年03月29日09時47分00秒
Last modified: 2019年09月15日12時54分47秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF584
トップページに戻る
Logged in as: unknown user (not login)