JustAnotherCatgirl

Eternal Mish Logist

Apr 2nd, 2023
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.75 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. typedef long long int64;
  4. typedef std::vector<int64> i64v;
  5.  
  6. /*
  7. HOW DOES THE ALGORITHM WORK (in short)
  8. 1. devide an array into trucks and calculate,
  9. how much profit they can bring if a: they are
  10. in the middle of sequence, b: if in the
  11. beginning, c: if they are at the end. calculated
  12. profits are stored in struct "profits".
  13. 2. now we have an array of all possible profits for
  14. all possible truck loads. all we have to do now is to
  15. find maximal sub-array sum, taking capacity
  16. of truck into account, as the step in iterations
  17. will be capacity, as well as the fact that truck
  18. can be either in the beginning, ending or in the
  19. middle of sequencr. The biggest calculated sum
  20. should give us the answer
  21. 3. p r o f i t :)
  22. */
  23.  
  24.  
  25. struct profits
  26. { //store possible profits for 1 vehicle & return ones needed
  27.     int64 all = 0, begin = 0, end = 0;
  28.  
  29.     void set(int64 nall, int64 nbegin, int64 nend)
  30.     {
  31.         all = nall;
  32.         begin = nbegin;
  33.         end = nend;
  34.     }
  35.  
  36.     int64 best(char place = 'm')
  37.     { //return needed
  38.         switch (place)
  39.         {
  40.         case 'm': return all;
  41.         case 'b': return all - begin;
  42.         case 'e': return all - end;
  43.         default: return 0;
  44.         }
  45.     }
  46.  
  47. };
  48.  
  49.  
  50. int64 task(uint64_t amount, uint64_t capacity, uint64_t cost, i64v list)
  51. { //passing <amount> with zeroes included already
  52.  
  53.     std::vector<profits> p(amount);
  54.  
  55.     //calculating all possible profits for all possible vehicles
  56.     for (int i = 0; i < amount - capacity; ++i)
  57.     { // O(capacity*amount) complexity
  58.         int64 currsum = 0, maxendsum = 0, maxbeginsum = 0, wholesum;
  59.  
  60.         for (int j = i; j < i + capacity; ++j)
  61.         { //biggest sum if in the end
  62.             currsum += list[j];
  63.             if (currsum > maxendsum) maxendsum = currsum;
  64.         }
  65.         wholesum = currsum; //whole sum
  66.         for (int j = i; j < i + capacity; ++j)
  67.         { //biggest sum if in the beginning
  68.             if (currsum > maxbeginsum) maxbeginsum = currsum;
  69.             currsum -= list[j];
  70.         }
  71.  
  72.         p[i].set(wholesum - cost, maxbeginsum - cost, maxendsum - cost);
  73.  
  74.     }
  75.  
  76.     //searching for sub-list with biggest sum (vehicle sequence)
  77.     int64 bestSum = 0;
  78.     for (int k = 0; k < capacity; ++k)
  79.     { // O(amount) complexity
  80.         int64 currentSum = 0;
  81.         size_t start_pos = 0 /*, stop_pos = i */;
  82.         int64 best_begin = p[0].best('b'), best_end;
  83.         for (int i = k; i < amount; i += capacity)
  84.         { //Kadane's algorithm with some tweaks
  85.           //// (probably very optimizable, but uh, who cares)
  86.             if (currentSum < 0)
  87.             {
  88.                 currentSum = 0;
  89.                 start_pos = i;
  90.                 best_begin = p[start_pos].best('b');
  91.             }
  92.             currentSum += p[i].best();
  93.  
  94.             best_end = p[i].best('e');
  95.  
  96.             int64 bests[4] = { currentSum, currentSum - best_begin,
  97.                 currentSum - best_end, currentSum - best_begin - best_end };
  98.  
  99.             int ITER_TO = 4;
  100.             if (start_pos == i) ITER_TO = 3; //exclude last element of "bests" if begin == end
  101.             for (int j = 0; j < ITER_TO; ++j)
  102.                 if (bests[j] > bestSum) bestSum = bests[j];
  103.         }
  104.     }
  105.  
  106.     return bestSum;
  107. }
  108.  
  109.  
  110. int main()
  111. {
  112.     uint64_t n, k, s;
  113.     std::cin >> n >> k >> s;
  114.  
  115.     i64v list(n + 2 * k);
  116.     //fill back & front with (k) zeroes,
  117.     //and middle with actual inputs
  118.     for (int i = 0; i < k; ++i)
  119.         list[i] = 0;
  120.     for (int i = k; i < n + k; ++i)
  121.         std::cin >> list[i];
  122.     for (int i = n + k; i < n + 2 * k; ++i)
  123.         list[i] = 0;
  124.  
  125.     std::cout << task(n + 2 * k, k, s, list);
  126.     return 0;
  127. }
  128. //why did i spend so much time on this bruuuh
Advertisement
Add Comment
Please, Sign In to add comment