Codeforces Round #584 - Dasha Code Championship - Elimination Round H問題 - Moving Walkways

Source

Codeforces Round #584 - Dasha Code Championship - Elimination Round H問題 (4000pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20190914-1)のコード

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: 2021年12月05日23時21分32秒
Last modified: 2019年09月15日12時54分47秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF584
トップページに戻る

Logged in as: unknown user (not login)

ログイン: