結果

問題 No.448 ゆきこーだーの雨と雪 (3)
ユーザー ikdikd
提出日時 2017-11-30 01:52:01
言語 D
(dmd 2.106.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,499 bytes
コンパイル時間 259 ms
コンパイル使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-14 20:17:26
合計ジャッジ時間 2,810 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Main.d(18): Error: `ch(md) ? ok : ng` must be surrounded by parentheses when next to operator `=`

ソースコード

diff # 

void main(){
  import std.stdio, std.string, std.conv, std.algorithm;

  int n, k; rd(n, k);
  auto t=new int[](n), d=new long[](n);
  foreach(i; 0..n) rd(t[i], d[i]);

  bool ch(long y){ // yよりむずいの全部解けるか
    for(int i=0, T=0; i<n; i++)if(d[i]>y){
      if(t[i]<T) return false;
      T=t[i]+k;
    }
    return true;
  }
  long ng=-1, ok=reduce!(max)(d);
  while(ok-ng>1){
    auto md=(ok+ng)/2;
    ch(md) ? ok : ng = md;
  }

  long mx1=ok;
  if(mx1==0){writeln(0); writeln(0); return;}
  int[] idx;
  auto ame=new bool[](n);
  for(int i=0, T=0; i<n; i++){
    if(d[i]>mx1) T=t[i]+k;
    else if(t[i]<T) ame[i]=true;
  }
  for(int i=n-1, T=t[$-1]; i>=0; i--){
    if(d[i]>mx1) T=t[i]-k;
    else if(t[i]>T) ame[i]=true;
  }
  foreach(int i; 0..n){
    if(d[i]<=mx1 && ame[i]==false) idx~=i;
  }


  auto m=idx.length;
  auto rec=new long[](m);
  if(m==0){
    writeln(mx1);
    writeln(reduce!((r, e)=>r+((e<=mx1)?e:0L))(0L, d));
    return;
  }
  rec[0]=d[idx[0]];
  for(int i=1, j=0; i<m; i++){
    chmax(rec[i], rec[i-1]);
    while(j<i && (t[idx[j]]+k)<=t[idx[i]]) j++;
    if(j==0) chmax(rec[i], d[idx[i]]);
    else chmax(rec[i], rec[j-1]+d[idx[i]]);
  }

  writeln(mx1);
  writeln(sum(d)-reduce!((r, e)=>r+((e>mx1)?e:0L))(0L, d)-rec[m-1]);
}

void chmax(T)(ref T x, T y){
  if(x<y) x=y;
}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}
0