Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- typedef long long int64;
- typedef std::vector<int64> i64v;
- /*
- HOW DOES THE ALGORITHM WORK (in short)
- 1. devide an array into trucks and calculate,
- how much profit they can bring if a: they are
- in the middle of sequence, b: if in the
- beginning, c: if they are at the end. calculated
- profits are stored in struct "profits".
- 2. now we have an array of all possible profits for
- all possible truck loads. all we have to do now is to
- find maximal sub-array sum, taking capacity
- of truck into account, as the step in iterations
- will be capacity, as well as the fact that truck
- can be either in the beginning, ending or in the
- middle of sequencr. The biggest calculated sum
- should give us the answer
- 3. p r o f i t :)
- */
- struct profits
- { //store possible profits for 1 vehicle & return ones needed
- int64 all = 0, begin = 0, end = 0;
- void set(int64 nall, int64 nbegin, int64 nend)
- {
- all = nall;
- begin = nbegin;
- end = nend;
- }
- int64 best(char place = 'm')
- { //return needed
- switch (place)
- {
- case 'm': return all;
- case 'b': return all - begin;
- case 'e': return all - end;
- default: return 0;
- }
- }
- };
- int64 task(uint64_t amount, uint64_t capacity, uint64_t cost, i64v list)
- { //passing <amount> with zeroes included already
- std::vector<profits> p(amount);
- //calculating all possible profits for all possible vehicles
- for (int i = 0; i < amount - capacity; ++i)
- { // O(capacity*amount) complexity
- int64 currsum = 0, maxendsum = 0, maxbeginsum = 0, wholesum;
- for (int j = i; j < i + capacity; ++j)
- { //biggest sum if in the end
- currsum += list[j];
- if (currsum > maxendsum) maxendsum = currsum;
- }
- wholesum = currsum; //whole sum
- for (int j = i; j < i + capacity; ++j)
- { //biggest sum if in the beginning
- if (currsum > maxbeginsum) maxbeginsum = currsum;
- currsum -= list[j];
- }
- p[i].set(wholesum - cost, maxbeginsum - cost, maxendsum - cost);
- }
- //searching for sub-list with biggest sum (vehicle sequence)
- int64 bestSum = 0;
- for (int k = 0; k < capacity; ++k)
- { // O(amount) complexity
- int64 currentSum = 0;
- size_t start_pos = 0 /*, stop_pos = i */;
- int64 best_begin = p[0].best('b'), best_end;
- for (int i = k; i < amount; i += capacity)
- { //Kadane's algorithm with some tweaks
- //// (probably very optimizable, but uh, who cares)
- if (currentSum < 0)
- {
- currentSum = 0;
- start_pos = i;
- best_begin = p[start_pos].best('b');
- }
- currentSum += p[i].best();
- best_end = p[i].best('e');
- int64 bests[4] = { currentSum, currentSum - best_begin,
- currentSum - best_end, currentSum - best_begin - best_end };
- int ITER_TO = 4;
- if (start_pos == i) ITER_TO = 3; //exclude last element of "bests" if begin == end
- for (int j = 0; j < ITER_TO; ++j)
- if (bests[j] > bestSum) bestSum = bests[j];
- }
- }
- return bestSum;
- }
- int main()
- {
- uint64_t n, k, s;
- std::cin >> n >> k >> s;
- i64v list(n + 2 * k);
- //fill back & front with (k) zeroes,
- //and middle with actual inputs
- for (int i = 0; i < k; ++i)
- list[i] = 0;
- for (int i = k; i < n + k; ++i)
- std::cin >> list[i];
- for (int i = n + k; i < n + 2 * k; ++i)
- list[i] = 0;
- std::cout << task(n + 2 * k, k, s, list);
- return 0;
- }
- //why did i spend so much time on this bruuuh
Advertisement
Add Comment
Please, Sign In to add comment