2015
04-13

# Magic Coupon

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 570    Accepted Submission(s): 130

Problem Description
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
The input file consists of several test cases. For each case, the first line contains the number of coupons NC, followed by a line with NC coupon integers. Then the next line contains the number of products NP, followed by a line with NP product values. Here
1<= NC, NP <= 10^6, and it is guaranteed that all the numbers will not exceed 10^7.
The input is finished by a negative NC.

Output
For each test case, your program must output to standard output. 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
4
3 2 6 1
3
2 6 3
-1

Sample Output
43
49

Source

#include "iostream"
#include "stdio.h"
#include "math.h"
#include "vector"
#include "queue"
#include "memory.h"
#include "algorithm"
#include "string"
using namespace std;
#define N 1000005
__int64 a1[N];
__int64 a2[N];

int main()
{
int n1,n2,i,j;
while(scanf("%d",&n1)!=EOF&&n1>=0)
{
for(i=0;i<n1;i++)
scanf("%I64d",&a1[i]);
scanf("%d",&n2);
for(i=0;i<n2;i++)
scanf("%I64d",&a2[i]);
sort(a1,a1+n1);//或者降序可以用sort(a1,a1+n1,greater<int>())
sort(a2,a2+n2);
i=0;
__int64 sum=0;
while(a1[i]<0&&a2[i]<0&&i<n1&&i<n2)
sum+=a1[i]*a2[i++];
i=n1-1,j=n2-1;
while(a1[i]>0&&a2[j]>0&&i>=0&&j>=0)
sum+=a1[i--]*a2[j--];
printf("%I64d\n",sum);
}
}


1. 这事未免也太扯淡了吧虽然我是很相信有灵异这回事的人但是如此蹊跷的事我想不会只你有一个人知道吧作为他的家人会不了解？就单说重庆一8岁小孩自称被僵尸附身这事都被各大媒体穷追不舍你这都变成猫了，还有可能变不回人了，还只能你一个人知道？现在都什么社会了？人的猎奇

2. 这事未免也太扯淡了吧虽然我是很相信有灵异这回事的人但是如此蹊跷的事我想不会只你有一个人知道吧作为他的家人会不了解？就单说重庆一8岁小孩自称被僵尸附身这事都被各大媒体穷追不舍你这都变成猫了，还有可能变不回人了，还只能你一个人知道？现在都什么社会了？人的猎奇

3. 这事未免也太扯淡了吧虽然我是很相信有灵异这回事的人但是如此蹊跷的事我想不会只你有一个人知道吧作为他的家人会不了解？就单说重庆一8岁小孩自称被僵尸附身这事都被各大媒体穷追不舍你这都变成猫了，还有可能变不回人了，还只能你一个人知道？现在都什么社会了？人的猎奇

4. 这事未免也太扯淡了吧虽然我是很相信有灵异这回事的人但是如此蹊跷的事我想不会只你有一个人知道吧作为他的家人会不了解？就单说重庆一8岁小孩自称被僵尸附身这事都被各大媒体穷追不舍你这都变成猫了，还有可能变不回人了，还只能你一个人知道？现在都什么社会了？人的猎奇

5. 这事未免也太扯淡了吧虽然我是很相信有灵异这回事的人但是如此蹊跷的事我想不会只你有一个人知道吧作为他的家人会不了解？就单说重庆一8岁小孩自称被僵尸附身这事都被各大媒体穷追不舍你这都变成猫了，还有可能变不回人了，还只能你一个人知道？现在都什么社会了？人的猎奇

6. 这事未免也太扯淡了吧虽然我是很相信有灵异这回事的人但是如此蹊跷的事我想不会只你有一个人知道吧作为他的家人会不了解？就单说重庆一8岁小孩自称被僵尸附身这事都被各大媒体穷追不舍你这都变成猫了，还有可能变不回人了，还只能你一个人知道？现在都什么社会了？人的猎奇

7. 这事未免也太扯淡了吧虽然我是很相信有灵异这回事的人但是如此蹊跷的事我想不会只你有一个人知道吧作为他的家人会不了解？就单说重庆一8岁小孩自称被僵尸附身这事都被各大媒体穷追不舍你这都变成猫了，还有可能变不回人了，还只能你一个人知道？现在都什么社会了？人的猎奇

8. 这事未免也太扯淡了吧虽然我是很相信有灵异这回事的人但是如此蹊跷的事我想不会只你有一个人知道吧作为他的家人会不了解？就单说重庆一8岁小孩自称被僵尸附身这事都被各大媒体穷追不舍你这都变成猫了，还有可能变不回人了，还只能你一个人知道？现在都什么社会了？人的猎奇

9. 这事未免也太扯淡了吧虽然我是很相信有灵异这回事的人但是如此蹊跷的事我想不会只你有一个人知道吧作为他的家人会不了解？就单说重庆一8岁小孩自称被僵尸附身这事都被各大媒体穷追不舍你这都变成猫了，还有可能变不回人了，还只能你一个人知道？现在都什么社会了？人的猎奇

10. 这事未免也太扯淡了吧虽然我是很相信有灵异这回事的人但是如此蹊跷的事我想不会只你有一个人知道吧作为他的家人会不了解？就单说重庆一8岁小孩自称被僵尸附身这事都被各大媒体穷追不舍你这都变成猫了，还有可能变不回人了，还只能你一个人知道？现在都什么社会了？人的猎奇