AtCoder Beginner Contest #116 D問題 - Various Sushi

Source

AtCoder Beginner Contest #116
問題文

問題概要

省略

解法

省略

cLay（version 20190715-1）のコード

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

int N, K, T[1d5], D[1d5];
{
  int i, j;
  ll res, tmp;
  
  set<int> used;
  multiset<int> deletable;

  rd(N,K,(T,D)(N));
  sortA(N, D, T);

  res = tmp = 0;
  for(i=N-1;i>=0;i--){
    if(used.count(T[i])){
      deletable.insert(D[i]);
    } else {
      used.insert(T[i]);
    }
    tmp += D[i];

    if(K==0){
      if(deletable.size()==0) break;
      tmp -= popFirst(deletable);
    } else {
      K--;
    }

    res >?= tmp + (ll)used.size() * (ll)used.size();
  }

  wt(res);
}

Current time: 2024年04月19日09時24分47秒
Last modified: 2019年07月15日22時54分16秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC116 ABC_D
トップページに戻る

Logged in as: unknown user (not login)