AtCoder Grand Contest #034 C問題 - Tests

Source

AtCoder Grand Contest #034
問題文

問題概要

省略

解法

省略

cLay（version 20190601-1）のコード

C++に変換後のコードはこちら

int N; ll X;
ll B[1d5], L[1d5], U[1d5];

ll gain[1d5], sum[100001];
{
  int i, ok;
  ll res, score, ini;
  int cnt, rem;

  rd(N, X, (B,L,U)(N));

  ini = 0;
  rep(i,N) ini -= B[i] * L[i];

  rep(i,N) gain[i] = (X - B[i]) * U[i] + B[i] * L[i];

  rep(i,N) gain[i] = -gain[i];
  sortA(N, gain, B, L, U);
  rep(i,N) gain[i] = -gain[i];
  rep(i,N) sum[i+1] = sum[i] + gain[i];
  
  res = bsearch_min[ll,res,0,N*X][
    ok = 0;
    cnt = res / X;
    rem = res % X;

    if(rem==0){
      score = ini + sum[cnt];
      if(score >= 0) ok = 1;
    } else {
      rep(i,N){
        score = ini;
        if(i < cnt) score += sum[cnt+1] - gain[i];
        else        score += sum[cnt];

        if(rem < B[i]) score += (rem - B[i]) * L[i] + B[i] * L[i];
        else           score += (rem - B[i]) * U[i] + B[i] * L[i];

        if(score >= 0){ ok = 1; break; }
      }
    }
  ](ok);

  wt(res);
}

cLay（version 20190601-1）のコード（二分探索を使わないバージョン）

C++に変換後のコードはこちら

int N; ll X;
ll B[1d5], L[1d5], U[1d5];

ll gain[1d5]; int ind[1d5];
{
  int i, j, k, ok;
  ll res = 0, s, tmp, ini;
  ll st, st1, st2;

  rd(N, X, (B,L,U)(N));

  ini = 0;
  rep(i,N) ini -= B[i] * L[i];

  rep(i,N) gain[i] = (((X - B[i]) * U[i] + B[i] * L[i]) << 17) + i;
  sortF(N, gain);
  rep(i,N){
    ind[i] = (gain[i] & ((1<<17)-1));
    gain[i] >>= 17;
  }
  reverse(gain, gain+N);
  reverse(ind, ind+N);

  s = ini;
  rep(k,N){
    if(s + gain[k] >= 0){
      st1 = -s;
      st2 = -(s+gain[k]);
      break;
    } else {
      s += gain[k];
    }
  }

  tmp = X;
  rep(j,k){
    i = ind[j];
    st = st2 + gain[j];
    if(st <= B[i] * L[i]){
      tmp <?= st /+ L[i];
    }else{
      st += B[i] * (U[i] - L[i]);
      tmp <?= st /+ U[i];
    }
  }
  rep(j,k,N){
    i = ind[j];
    st = st1;
    if(st <= B[i] * L[i]){
      tmp <?= st /+ L[i];
    }else{
      st += B[i] * (U[i] - L[i]);
      tmp <?= st /+ U[i];
    }
  }

  res = X * k + tmp;
  wt(res);
}

Current time: 2024年04月19日02時50分02秒
Last modified: 2019年06月03日02時58分54秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC034 AGC_C
トップページに戻る

Logged in as: unknown user (not login)