Problem Analysis and Solution

Given two arrays, the goal is to pair elements from each array to maximize the sum of their products. Since positive multiplied by positive yields positive, and negative multiplied by negative also yields positive, we can seperate both arrays into positive and negative components.

The optimal strategy is to pair large positive numbers together and large absolute values of negative numbers together. Remaining elements (requiring one positive and one negative) should pair large absolute values with small ones to minimize negative contributions.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<long long> positiveA, negativeA;
vector<long long> positiveB, negativeB;

int main() {
    int n, m;
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        long long val;
        cin >> val;
        if(val >= 0) positiveA.push_back(val);
        else negativeA.push_back(val);
    }
    
    for(int i = 0; i < m; i++) {
        long long val;
        cin >> val;
        if(val >= 0) positiveB.push_back(val);
        else negativeB.push_back(val);
    }
    
    sort(positiveA.rbegin(), positiveA.rend());
    sort(negativeA.begin(), negativeA.end());
    sort(positiveB.rbegin(), positiveB.rend());
    sort(negativeB.begin(), negativeB.end());
    
    long long result = 0;
    
    for(int i = 0; i < positiveA.size(); i++) {
        if(i < positiveB.size()) 
            result += positiveA[i] * positiveB[i];
        else 
            result += positiveA[i] * negativeB[negativeB.size() - (i - positiveB.size()) - 1];
    }
    
    for(int i = 0; i < negativeA.size(); i++) {
        if(i < negativeB.size()) 
            result += negativeA[i] * negativeB[i];
        else 
            result += negativeA[i] * positiveB[positiveB.size() - (i - negativeB.size()) - 1];
    }
    
    cout << result << endl;
    return 0;
}

Efficient Airport Queue Processing

This problem involves processing queries to determine how many people can board a vehicle based on weight constraints. The solution employs binary search combined with Fenwick trees for efficient range queries.

We sort all weights and maintain two Fenwick trees: one for cumulative weights and another for counting people. For each query, we find the maximum number of people whose total weight doesn't exceed the remaining capacity after including the current person.

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

class FenwickTree {
private:
    vector<long long> tree;
public:
    FenwickTree(int size) : tree(size + 1, 0) {}
    
    void update(int index, long long value) {
        for(; index < tree.size(); index += index & -index)
            tree[index] += value;
    }
    
    long long query(int index) {
        long long sum = 0;
        for(; index > 0; index -= index & -index)
            sum += tree[index];
        return sum;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int testCases;
    cin >> testCases;
    
    while(testCases--) {
        int n, capacity;
        cin >> n >> capacity;
        
        vector<int> weights(n);
        vector<pair<int, int>> sortedWeights(n);
        
        for(int i = 0; i < n; i++) {
            cin >> weights[i];
            sortedWeights[i] = {weights[i], i};
        }
        
        sort(sortedWeights.begin(), sortedWeights.end());
        vector<int> position(n);
        
        for(int i = 0; i < n; i++)
            position[sortedWeights[i].second] = i + 1;
        
        FenwickTree weightTree(n), countTree(n);
        vector<int> answers(n);
        
        for(int i = 0; i < n; i++) {
            int remaining = capacity - weights[i];
            int left = 0, right = n;
            
            while(left < right) {
                int mid = (left + right + 1) / 2;
                if(weightTree.query(mid) <= remaining)
                    left = mid;
                else
                    right = mid - 1;
            }
            
            answers[i] = i - countTree.query(left);
            weightTree.update(position[i], weights[i]);
            countTree.update(position[i], 1);
        }
        
        for(int i = 0; i < n; i++)
            cout << answers[i] << " ";
        cout << "\n";
    }
    
    return 0;
}

Candy Distribution Optimization

This problem requires dividing a sequence into k segments such that the maximum segment sum is minimized. We use binary search combined with dynamic programming and Fenwick tree optimization.

Binary Search Approach

We binary search for the minimum possible maximum segment sum. For each candidate value, we check if the sequence can be divided into k segments where each segment sum doesn't exceed the candidate.

#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>
using namespace std;

const long long INF = 1e18;

class SegmentTree {
private:
    vector<int> tree;
    int size;
public:
    SegmentTree(int n) : size(n), tree(2 * n, INT_MIN) {}
    
    void update(int index, int value) {
        index += size;
        tree[index] = value;
        for(index /= 2; index > 0; index /= 2)
            tree[index] = max(tree[2 * index], tree[2 * index + 1]);
    }
    
    int query(int left, int right) {
        left += size;
        right += size;
        int result = INT_MIN;
        
        while(left <= right) {
            if(left % 2 == 1) result = max(result, tree[left++]);
            if(right % 2 == 0) result = max(result, tree[right--]);
            left /= 2;
            right /= 2;
        }
        return result;
    }
};

bool canDivide(vector<long long>& prefix, int k, long long maxSum) {
    int n = prefix.size() - 1;
    vector<long long> values;
    
    for(int i = 0; i <= n; i++) {
        values.push_back(prefix[i]);
        values.push_back(prefix[i] - maxSum);
    }
    
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    
    auto getIndex = [&](long long val) {
        return lower_bound(values.begin(), values.end(), val) - values.begin();
    };
    
    SegmentTree segTree(values.size());
    vector<int> dp(n + 1, INT_MIN);
    dp[0] = 0;
    segTree.update(getIndex(prefix[0]), dp[0]);
    
    for(int i = 1; i <= n; i++) {
        int idx = getIndex(prefix[i] - maxSum);
        dp[i] = segTree.query(idx, values.size() - 1) + 1;
        if(dp[i] >= k) return true;
        segTree.update(getIndex(prefix[i]), dp[i]);
    }
    return false;
}

int main() {
    int testCases;
    cin >> testCases;
    
    while(testCases--) {
        int n, k;
        cin >> n >> k;
        vector<long long> arr(n + 1), prefix(n + 1, 0);
        
        for(int i = 1; i <= n; i++) {
            cin >> arr[i];
            prefix[i] = prefix[i - 1] + arr[i];
        }
        
        if(k == 1) {
            long long minPrefix = INF;
            for(int i = 1; i <= n; i++)
                minPrefix = min(minPrefix, prefix[i]);
            cout << minPrefix << "\n";
            continue;
        }
        
        long long left = -1e14, right = 1e14;
        while(left < right) {
            long long mid = left + (right - left) / 2;
            if(canDivide(prefix, k, mid))
                right = mid;
            else
                left = mid + 1;
        }
        cout << left << "\n";
    }
    return 0;
}

Gem Processing Optimization

This problem involves maximizing profit from processing gems on two conveyor belts. We use dynamic programming with optimization techniques for handling large input sizes.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

long long maxThree(long long a, long long b, long long c) {
    return max(a, max(b, c));
}

void computeDP(vector<vector<long long>>& dp, 
               vector<long long>& a, vector<long long>& b,
               vector<long long>& d, vector<long long>& e,
               vector<vector<long long>>& c,
               int l1, int r1, int l2, int r2) {
    
    for(int i = l1; i <= r1; i++)
        dp[i][l2 - 1] = dp[i - 1][l2 - 1] + d[i];
    
    for(int j = l2; j <= r2; j++)
        dp[l1 - 1][j] = dp[l1 - 1][j - 1] + e[j];
    
    for(int i = l1; i <= r1; i++) {
        for(int j = l2; j <= r2; j++) {
            dp[i][j] = maxThree(
                dp[i - 1][j] + d[i],
                dp[i][j - 1] + e[j],
                dp[i - 1][j - 1] + a[i] + b[j] - c[i][j]
            );
        }
    }
}

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    
    vector<long long> a(n + 1), b(m + 1), d(n + 1), e(m + 1);
    vector<vector<long long>> c(n + 1, vector<long long>(m + 1));
    
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) cin >> d[i];
    for(int i = 1; i <= m; i++) cin >> e[i];
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> c[i][j];
    
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
    
    while(q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        computeDP(dp, a, b, d, e, c, l1, r1, l2, r2);
        cout << dp[r1][r2] << "\n";
    }
    
    return 0;
}