main.cpp (2510B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 #include <queue> 7 8 #define ll long long 9 10 // computer game 11 // current game can be modeled as a straight line 12 // start at point 0 13 // n monsters trying to kill you 14 // ith monster has a_i health starts at point x_i 15 16 // every second: 17 // fire up to k bullets at monsters each hits one monster for 1 damage 18 // 0 or less health monsters die 19 // alive move one point closer 20 // if monster reaches you die 21 // can you survive? 22 // we will always want to target nearest and if at all possible not waste bullets 23 // 24 25 // n = 3, k = 2 26 // healths = [1 2 3] 27 // positions = [-1 2 3] 28 29 // since we are at 0 we can normalize by distance 30 31 // healths = [1 2 3] 32 // distances = [1 2 3] 33 34 // we shoot nearest once, second once 35 // they move, we shoot second once and third once 36 // they move, we kill final, return "YES" 37 38 // the issue here is that we can get fucked by large numbers, computationally 39 // instead we'll want to consider how many shots to kill nearest, take that many steps with a remainder 40 // and then move all of them. 41 42 using namespace std; 43 44 int main() { 45 ll testCases, n, k, current; 46 cin >> testCases; 47 48 for(ll z = 0; z < testCases; ++z) { 49 cin >> n; 50 cin >> k; 51 52 vector<ll> health {}; 53 vector<ll> distance {}; 54 55 vector<pair<ll,ll>> distHealth {}; 56 57 for(ll i = 0; i < n; ++i) { 58 cin >> current; 59 health.push_back(current); 60 } 61 62 for(ll i = 0; i < n; ++i) { 63 cin >> current; 64 65 if (current < 0) { 66 distance.push_back(current * -1); 67 } 68 else { 69 distance.push_back(current); 70 } 71 } 72 73 for(ll i = 0; i < n; ++i) { 74 pair<ll,ll> current {distance[i], health[i]}; 75 distHealth.push_back(current); 76 } 77 78 sort(distHealth.begin(), distHealth.end()); 79 bool ck = true; 80 long long shot = 0; 81 82 for(ll i = 0; i < distHealth.size(); ++i) { 83 ll targetDistance = distHealth[i].first; 84 ll targetHealth = distHealth[i].second; 85 if((k*targetDistance) - shot < targetHealth) { 86 ck = false; 87 break; 88 } else { 89 shot += targetHealth; 90 } 91 } 92 93 94 if(!ck) { 95 cout << "NO" << endl; 96 } else { 97 cout << "YES" << endl; 98 } 99 } 100 }