pat

题目

The magic shop in Mars is offering some magic coupons. Each coupon has an integer $N$ printed on it, meaning that when you use this coupon with a product, you may get $N$ times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you apply a coupon with a positive $N$ to this bonus product, you will have to pay the shop N times the value of the bonus product... but hey, magically, they have some coupons with negative $N$'s!

For example, given a set of coupons { 1 2 4 −1 }, and a set of product values { 7 6 −2 −3 } (in Mars dollars M $ ) where a negative value corresponds to a bonus product. You can apply coupon 3 (with N being 4) to product 1 (with value M $ 7) to get M $ 28 back; coupon 2 to product 2 to get M $ 12 back; and coupon 4 to product 4 to get M $3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M $ 12 to the shop.

Each coupon and each product may be selected at most once. Your task is to get as much money back as possible.

Input Specification:
Each input file contains one test case. For each case, the first line contains the number of coupons $N_​C$
​​ , followed by a line with $N_C$
​​ coupon integers. Then the next line contains the number of products $N_P$
​​ , followed by a line with $N_P$
​​ product values. Here $1≤N_C
​​ ,N_P ≤10^5$
​​ , and it is guaranteed that all the numbers will not exceed $2^{30}$
​​ .

Output Specification:
For each test case, simply print in a line the maximum amount of money you can get back.

Sample Input:

4
1 2 4 -1
4
7 6 -2 -3

Sample Output:

43

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
vll NC, NP;
bool (ll a, ll b){ return a > b; }
int main(){
    int Nc, Np;
    ll tc, tp;
    scanf("%d", &Nc);
    for(int i = 0;i < Nc;i++){
        scanf("%lld", &tc);
        NC.push_back(tc);
    }
    scanf("%d", &Np);
    for(int i = 0;i < Np;i++){
        scanf("%lld", &tp);
        NP.push_back(tp);
    }
    sort(NC.begin(), NC.end(), cmp);
    sort(NP.begin(), NP.end(), cmp);
    int posC = 0, posP = 0, flag = 0;
    ll sum = 0;
    while(posC < NC.size() && posP < NP.size() && NC[posC] > 0 && NP[posP] > 0)
        sum += NC[posC++]  NP[posP++];
    posC = NC.size() - 1; posP = NP.size() - 1;
    while(posC > 0 && posP > 0 && NC[posC] < 0 && NP[posP] < 0)
        sum += NC[posC--]  NP[posP--];
    printf("%lld", sum);
    return 0;
}