Maximum Possible Sweetness:
Chef goes to a candy store that sells N different candies. For each candy, we know its price and sweetness. Chef has D dollars and can take a maximum of 2 candies, one in each hand. Find the maximum total sweetness he can buy under the given constraints.
NOTE: Since the input-output is large, prefer using fast input-output methods.
Input Format
• First line will contain 2 space separated integers N and D, the number of different candies and the amount of money Chef has.
• Second line contains N space separated integers P1 ,P2,...,PN, where Pi is the price of the ith candy.
• Third line contains N space separated integers S1,S2 ,...,SN, where Si is the sweetness of the ith candy.
Output Format
Output in a single line, the maximum total sweetness Chef can buy with the money he has, and with at most two candies.
Constraints
• 1≤N≤105
• 1≤D≤109
• 1 Pi, Si≤109
• Sum N over all testcases is atmost 106.
Sample Input:
2 10
1 2
2 1
Sample Output:
3
Explanation:
Chef can collect both the candies available with the money he has.
Sample Input
2 10
1 2
2 1
Sample Output
3
Program:
#C
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int first;
int second;
} pair;
int cmp(const void* a, const void* b) {
pair* p1 = (pair*) a;
pair* p2 = (pair*) b;
return p1->first - p2->first;
}
int main() {
int N, D;
scanf("%d %d", &N, &D);
pair merge[N];
for (int i = 0; i < N; i++) {
scanf("%d", &merge[i].first);
}
for (int i = 0; i < N; i++) {
scanf("%d", &merge[i].second);
}
qsort(merge, N, sizeof(pair), cmp);
if (merge[0].first > D) {
printf("0\n");
}
int q[N];
int head = 0;
int tail = 0;
q[tail++] = 0;
int maxAns = merge[0].second;
for (int i = 1; i < N; i++) {
int temp = merge[i].second;
while (head < tail && merge[q[tail-1]].first + merge[i].first > D) {
tail--;
}
if (head < tail) {
temp += merge[q[tail-1]].second;
} else if (merge[i].first > D) {
temp = 0;
}
maxAns = temp > maxAns ? temp : maxAns;
merge[i].second = merge[i].second > merge[i-1].second ? merge[i].second : merge[i-1].second;
q[tail++] = i;
}
printf("%d\n", maxAns);
return 0;
}
#Python:
Explanation:
Implementation of a solution to a problem that takes input of integer T, the number of test cases. Then for each test case, it takes inputs N and D representing the size of the array and the maximum allowed value of the sum of first and second integers of a pair, respectively. The next two lines of input take in N integers as the first elements of the pairs, and the next line takes N integers as the second elements of the pairs.
The program then sorts the pairs based on the first element using the qsort function in C standard library. If the first element of the smallest pair is greater than D, the program prints 0 and goes to the next test case.
The program initializes an empty q as a queue (implemented using an array) and adds the index of the first element of the sorted array to it. It also sets maxAns to the second element of the first pair.
Then for each index starting from 1, the program calculates the sum of the first and second element of the current pair, and checks if it is larger than D. If it is, it sets the temporary value of the pair's second element to 0. If the queue is not empty, the program adds the second element of the pair at the end of the queue if the sum of the first elements of the last element of the queue and the current pair is less than or equal to D. If the queue is not empty, the program updates the temporary value of the second element of the pair as the sum of the second element of the pair and the second element of the last pair in the queue. The program then checks whether the temporary value is larger than maxAns and sets maxAns to it if it is. Finally, the program updates the second element of the current pair to the maximum of its own second element and the second element of the previous pair. It then adds the index of the current pair to the end of the queue.
After iterating over all indices of the sorted array, the program prints the value of maxAns.
0 Comments