Official

D - 冒険者の装備選び / Adventurer's Equipment Selection Editorial by physics0523 Editorial for printing


装備品はいくつでも身に付けられ、 \(W_i, S_i \ge 0\) なので身に着けて損することもありません。
よって、全ての装備品を装備した状態をシミュレートし、防御力の合計が \(K\) 以上なら \(S_i\) の総和が、そうでなければ -1 が答えです。

時間計算量は \(O(N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,K,tW=0,tS=0;
  cin >> N >> K;
  while(N--){
    int W,S;
    cin >> W >> S;
    tW+=W; tS+=S;
  }
  if(K<=tW){cout << tS << "\n";}
  else{cout << "-1\n";}
  return 0;
}

posted:
last update: