AtCoder 競技プログラミングの鉄則　演習問題集 C19問題 - Gasoline Optimization Problem

Source

AtCoder 競技プログラミングの鉄則　演習問題集
問題文

問題概要

省略

解法

省略

cLay（version 20221122-1）のコード

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

int @N, @L, @K; int A[N+1]; ll C[N+1]; rd((A,C)(N)); A[N] = L;
ll res = 0; int g = K, p = 0, d;
int ss = 0, se = 0, sp[N]; ll sc[N];

rep(i,N+1){
  g -= A[i] - p;
  p = A[i];

  while(g < 0){
    if(ss == se) wt(-1), return 0;
    d = (K - (p - sp[ss])) - g;
    d <?= -g;
    if(d <= 0) ss++, continue;
    res += d * sc[ss];
    g += d;
  }
  
  while(ss < se && sc[se-1] >= C[i]) se--;
  sp[se] = A[i]; sc[se] = C[i]; se++;
}

wt(res);

Current time: 2024年05月05日23時56分47秒
Last modified: 2022年11月23日15時25分38秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：