algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 }