結果

問題 No.448 ゆきこーだーの雨と雪 (3)
ユーザー ikdikd
提出日時 2017-11-30 01:36:06
言語 D
(dmd 2.106.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,538 bytes
コンパイル時間 122 ms
コンパイル使用メモリ 6,816 KB
最終ジャッジ日時 2024-11-14 20:17:27
合計ジャッジ時間 898 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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;
  for(int i=0, j=-1; i<n; i++)if(d[i]>mx1){
    for(int x=j+1; x<i; x++){
      if(j>=0){
        if(t[j]+k<=t[x] && t[x]+k<=t[i]) idx~=x;
      }else{
        if(t[x]+k<=t[i]) idx~=x;
      }
    }
    j=i;
  }
  for(int i=n-1; i>=0; i--)if(d[i]>mx1){
    for(int j=i+1; j<n; j++){
      if(t[i]+k<=t[j]) idx~=j;
    }
    break;
  }

  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