Zcmu--5015: complete the task

Description

zbj Recently started playing a single game , This game is very interesting , There is no limit to the acceptance of all tasks , So he took all the tasks he could take at one time , But at this time, he found a very serious problem , In total, he accepted n A mission , Each task has the remaining completion time and the monetary reward of this task

Now for the convenience of ,zbj Suppose the current time is 0, He knows the remaining completion time and completion money of each task , And the time to complete a task is 1.

I hope you can tell him how to complete the task to get as much money as possible

Input

The first line contains an integer n, Expressing common ownership n A mission .
The second line contains n It's an integer ai, It means the first one i The remaining completion time of this task
The third line contains n It's an integer bi, It means the first one i Monetary reward for this task
(1<=ai,bi,n<=1000)

Output

The output contains an integer , It means the most money you can get .

Sample Input

3

1  3  1

6  2  3

Sample Output

8

analysis ： Initially, it must be sorted from large to small according to the bonus , If the bonus is the same, the remaining time is small , Then open an array m To record the number of i Whether a time point is occupied , Then traverse a wave , If at present ti The time point is not occupied , Then occupy ti At this point in time , If occupied , We just keep moving forward to find a time point that is not occupied , Just take it , In this way, we can maximize the total amount .

#include <stdio.h>
#include <algorithm>
using namespace std;
struct s
{
	int t,v;
	bool operator<(const s&x)const{		// Prioritize according to bonus , Second in time  
		if(v!=x.v) return v>x.v;
		return t<x.t;
	}	
}a[1005];
int m[1005]={0};// Record No. i Whether the time points are occupied ,0 Indicates not used ,1 Indicates that... Has been used  
int main()
{
	int n,i,s=0,p;
		scanf("%d",&n);
		for(i=0;i<n;i++) scanf("%d",&a[i].t);
		for(i=0;i<n;i++) scanf("%d",&a[i].v);
		sort(a,a+n);
		for(i=0;i<n;i++){
			p=a[i].t;
			if(m[p]==0) m[p]=1,s+=a[i].v;// At present p The time point is not occupied , Occupied and marked 1 
			else{	// At present p Already occupied , Move forward  
				while(m[p]==1&&p>0) p--;	// Until you find an unused node , sign out  
				if(p>0) m[p]=1,s+=a[i].v;	// Because of time >0, Set a boundary  
			}
		}
		printf("%d\n",s);
	return 0;
}