두더지 놀이 중 석유

http://exam.upc.edu.cn/problem.php?id=5502
위대 한 2320 선배 들 은 두더지 놀 이 를 특히 좋아한다.이 게임 이 시작 되면 바닥 에서 두더지 가 튀 어 나온다.망치 로 두더지 들 을 두 드 려 도 된다.두더지 마다 두 드 려 지면 해당 하 는 게임 점수 가 증가한다.그러나 모든 두더지 가 땅 에 한동안 만 나타 나 고(사라 진 후 다 시 는 나타 나 지 않 는 다)두더지 마다 0 시 에 튀 어 나 오지 만 머 무 르 는 시간 이 다 를 수 있 으 며 두더지 마다 두 드 려 서 늘 어 나 는 게임 점수 도 다 를 수 있다.최근 2320 선배 들 은 두더지 한 마 리 를 1 초 만 두 드 리 는 등 이 게임 을 자주 한다.그 는 어떻게 두 드 려 서 총 점 을 가장 크게 할 수 있 을 지 생각 하고 있다.
입력
입력 은 3 줄 을 포함 합 니 다.첫 번 째 줄 은 하나의 정수 n(1<=n<=100000)을 포함 합 니 다.n 개의 두더지 가 땅 에서 튀 어 나 왔 음 을 표시 합 니 다.두 번 째 줄 n 개 는 빈 칸 으로 구 분 된 정 수 는 두더지 가 튀 어 나 온 후 머 무 르 는 시간(Maxt<=50000)을 표시 합 니 다.세 번 째 줄 n 개 는 빈 칸 으로 구 분 된 정 수 는 두더지 가 두 드 리 면 증가 하 는 점수 v(v<1000)를 표시 합 니 다.줄 마다 i 번 째 숫자 는 i 번 째 두더지 의 정 보 를 나타 낸다.
출력
출력 은 한 줄 의 정수 만 있 고 얻 을 수 있 는 최대 게임 총 점 수 를 표시 합 니 다.
 
샘플 입력

5
5 3 6 1 4
7 9 2 1 5

샘플 출력

24

제시 하 다.
30%의 데이터 보증 n<=100,t<=500,v<=50 60%의 데이터 보증 n<=10000,t<=3000,v<=500 100%의 데이터 보증 n<=100000,t<=5000,v<=1000
중국 어 는 주제 의 뜻 을 말 하지 않 는 다.욕심 이 좀 있 는 생각 은 최대 에서 최소(시간)까지 하기 때문에 뒤에서 앞으로 나 아 갑 니 다.
이 문 제 는 그 자체 가 어렵 지 않 습 니 다.여러 가지 방법 이 있 습 니 다.그런데 저 는 생각 하지 못 했 습 니 다.오전 에 방금 본 set 의 용법(사용자 정의 로 큰 것 부터 작은 것 까지 정렬 할 수 있 습 니 다)을 set 로 쓰 려 고 했 습 니 다.한 시간 이 걸 렸 습 니 다.안 타 깝 게 도 set 는 중복 되 는 요 소 를 저장 할 수 없다 는 것 을 알 게 되 었 습 니 다.오랫동안 찾 아 보 았 는데 multiset 의 연장 입 니 다.중복 되 는 요 소 를 저장 할 수 있 지만 wa 입 니 다.자 료 를 찾 아 보 니 삭제 하 자마자 같은 요 소 를 모두 삭제 하고 lower 도입bound()(같은 요소 의 맨 앞 에 있 는 것 을 찾 습 니 다).첫 번 째 요 소 를 삭제 할 수 있 습 니 다.
#include #include #include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) #define ll long long using  namespace std; int maxn (int a,int b,int c){return max(max(a,b),max(b,c));} struct node {      ll time,cost; }a[100005]; struct cmp{      bool operator()(node a,node b)             {                 if(a.cost==b.cost) a.time>b.time;                 return a.cost>b.cost;             } }; multisetsum; ll cmp(node a,node b) {     if(a.time==b.time) a.cost     return a.time } int main() {     int n;     scanf("%d",&n);     for(int i=1;i<=n;i++)     {         scanf("%lld",&a[i].time);     }     for(int i=1;i<=n;i++)     {         scanf("%lld",&a[i].cost);     }     sort(a+1,a+n+1,cmp);     int tim=a[n].time;     long long cos=0;     int i=n;     while(i>=0&&tim>0)     {         if(a[i].time>=tim)         {             sum.insert(a[i]);             i--;         }         else {             if(sum.empty()==true) {                 tim--; continue;             }             multiset::iterator temp=sum.begin();            //  multiset::iterator temp1=sum.begin();            /* for(temp=sum.begin;temp!=sum.rend();temp++)             {                 if(temp->cost==temp1.cost&&temp->time==temp1.cost&&tim>=a[i].time)                 {                     cos+=temp->cost;tim--;                 }             }*/              cos+=temp->cost;             sum.erase(sum.lower_bound(*temp));             tim--;         }     }     printf("%lld",cos);     return 0;  }