2019年06月03日02時09分10秒に更新されたバージョンを表示しています．
最新のページはこちらをご覧ください．

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);
}

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

Logged in as: unknown user (not login)