yukicoder No.1012 - 荷物収集

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLay（version 20200321-1）のコード

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

int N, Q;
ll X[1d5], W[1d5], P[1d5];
int ind[1d5];
ll res[1d5];

{
  int k = 0;
  ll lef = 0, rig = 0, now = 0, tmp = 0;
  rd(N,Q,(X,W)(N),P(Q));
  rep(i,Q) ind[i] = i;
  sortA(N,X,W);
  sortA(Q,P,ind);

  rep(i,N){
    tmp += X[i] * W[i];
    rig += W[i];
  }

  rep(i,Q){
    while(k < N && X[k] < P[i]){
      tmp += (X[k] - now) * (lef - rig);
      now = X[k];
      rig -= W[k];
      lef += W[k];
      k++;
    }
    tmp += (P[i] - now) * (lef - rig);
    now = P[i];
    res[ind[i]] = tmp;
  }
  wtLn(res(Q));
}

Current time: 2024年04月21日01時23分49秒
Last modified: 2020年03月21日16時21分03秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)