Official
D - 冒険者の装備選び / Adventurer's Equipment Selection Editorial
by
D - 冒険者の装備選び / Adventurer's Equipment Selection Editorial
by
physics0523
装備品はいくつでも身に付けられ、 \(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;
}
