main.cpp (2190B)
1 #include <iostream> 2 #include <vector> 3 4 long long vecSum(std::vector<long long> inp) { 5 long long sm = 0; 6 for(auto i : inp) { 7 sm += i; 8 } 9 return sm; 10 } 11 12 void printVec(std::vector<long long> inp) { 13 for(long long i = 0 ; i < inp.size(); ++i) { 14 std::cout << inp[i] << " "; 15 } 16 std::cout << std::endl; 17 18 } 19 20 long long solve(std::vector<long long> nums, int health, int reloadTime) { 21 22 std::vector<long long> minPrefixInc {}; 23 24 long long min = nums[0]; 25 26 for(int i = 0; i < nums.size(); ++i) { 27 if(nums[i] < min) { 28 min = nums[i]; 29 } 30 minPrefixInc.push_back(min); 31 } 32 33 std::vector<long long> maxPostfixExc (nums.size() - 1); 34 long long max = nums[nums.size()-1]; 35 36 for(int i = nums.size()-2; i >= 0; --i) { 37 maxPostfixExc[i] = max; 38 if(nums[i] > max) { 39 max = nums[i]; 40 } 41 } 42 43 //printVec(nums); 44 //printVec(maxPostfixExc); 45 //printVec(minPrefixInc); 46 47 long long vs = vecSum(nums); 48 long long target = health % vs; 49 50 long long running = 0; 51 int required = 1; 52 53 if(target != 0) { 54 for(int i = 0; i < nums.size()-1; ++i) { 55 running += nums[i]; 56 long long bestChoiceDelta = maxPostfixExc[i] - minPrefixInc[i]; 57 if(running + bestChoiceDelta >= target) { 58 break; 59 } else { 60 required += 1; 61 } 62 } 63 } else { 64 required = 0; 65 } 66 67 long long base = (health / vs) * (reloadTime + nums.size()); 68 if(target == 0) { 69 base = ((health / vs) * (nums.size())) + (((health / vs) - 1) * reloadTime); 70 } 71 72 73 return required + base; 74 } 75 76 int main() { 77 78 int testCount, arrElement, nElements, reloadTime, health; 79 std::cin >> testCount; 80 for(int i = 0; i < testCount; ++i) { 81 std::cin >> nElements; 82 std::cin >> health; 83 std::cin >> reloadTime; 84 std::vector<long long> current {}; 85 for(int x = 0; x < nElements; ++x) { 86 std::cin >> arrElement; 87 current.push_back(arrElement); 88 } 89 std::cout << solve(current, health, reloadTime) << std::endl; 90 } 91 }