PID553 / [IOI09]Garage
题目描述

一个停车场里面有N个停车位,编号从1到N。停车场每天开始时是空的然后按照如下规则操作:当一辆车到达停车场的时候,员工检查停车场是否有空车位,如果没有,这辆车会停留在入口直到一个停车位空出来。如果有空停车位,或者直到某个车位空出来了,这辆车会停进那个停车位。如果有多个停车位是空的,这辆车会停在编号最小的车位,如果在有车等待的时候更多的车到达了停车场,他们会按照他们到达的顺序排成一列,然后当有空位出现的时候,队列中的第一辆车会停进那个空位。

停车费用等于车辆的重量乘上停车位的系数,停车费用与停车时间无关。

停车场的操作员知道会有M辆车到达,以及它们到达和离开的顺序。请你帮助他计算停车场能获得的收益。

数据规模

1<=N<=100 , 1<=M<=2000 , 1<=R_s<=100(停车位s的价格) , 1<=W_k<=10000(汽车k的重量)

输入格式

第一行N,M

接下来N行描述了停车位的价格,其中第s行包含一个整数R_s,表示停车位s的价格。

接下来的M行描述了汽车的重量,汽车从1到M编号,这M行中的第k行包含一个整数W_k,表示汽车k的重量。

接下来的2*M行按照时间先后描述了所有汽车到达和离开的顺序。整数i表示汽车i到达,负数-i表示汽车i离开。没有任何一辆车离开时间早于到达时间,每辆车在这个序列中只出现两次且一次到达一次离开。没有车会从停车场入口的等待队列中离开。

输出格式

一个整数,表示停车场的总收入。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论