#2 pointers

Solutions A simple solution consists in sorting both sequences and running two nested for loops to calculate the possible costs. Although this solution is \(O((n+m) \cdot log(n+m)) + n \cdot m)\), it's acceptable since the input is small: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int s, n, m; cin >> s >> n >> m; vector<int> k(n); copy_n(istream_iterator<int>(cin), n, begin(k)); vector<int> u(m); copy_n(istream_iterator<int>(cin), m, begin(u)); sort(begin(k), end(k), greater<>{}); sort(begin(u), end(u), greater<>{}); auto cost = -1; for(auto i : k) { for (auto j : u) { if (i+j<=s) cost = max(cost, i+j); } } cout << cost; Linq-based solution, with cartesian product (by fabrizio_sanmar1): [Read More]

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order, in linear time. Input Format The first line contains N, the length of the array. The second line contains N space-separated integers, the elements of the array. Constraints \(1 \leq N \leq 10^6\) \(-10^3 \leq A[i] \leq 10^3\) Output Format Print the array of the squares of each number, also in sorted non-decreasing order. [Read More]