問題の説明#
ある日、子供たちが設計したゲームがコンピュータチームによって無視されたため、VIP999 は非常に不満でした。慰めと励ましを示すために、VIP999 は彼を一度「年年大丰收」に連れて行くことに決めました。誠意を示すために、彼は自分で釣りに行くことにしました。
しかし、NOIP2013 の準備をしなければならないため、z 先生は彼に H 時間の余暇時間しか与えませんでした。水平な道路に沿って n 個の池があり、左から右に 1、2、3、...、n と番号が付けられています。
VIP は効率を重視する子供ですので、この時間を最大限に利用してできるだけ多くの魚を釣りたいと思っています。彼は湖 1 から出発し、右に向かって進み、いくつかの湖で一定の時間停止して魚を釣り、最後にある湖で釣りを終了します。彼は第 i 湖から第 i+1 湖までの移動に 5×Ti 分かかることを測定し、第 i 湖で停止した場合、最初の 5 分間で Fi 匹の魚を釣ることができ、その後の 5 分ごとに釣れる魚の数が Di 匹減少することを測定しました。減少後の魚の数が 0 より小さい場合、減少後の魚の数は 0 とします。問題を単純化するため、他の人が釣りをすることはなく、他の要因が彼が望む数の魚を釣ることに影響を与えることはありません。最大の魚の数を釣るためにプログラムを作成してください。
入出力形式#
入力形式：
1 行目：湖の数 n。
2 行目：時間 h（時間）。
3 行目：n 個の数、f1、f2、… fn。
4 行目：n 個の数、d1、d2、….dn。
5 行目：n-1 個の数、t1、t2、….tn?1
出力形式：
1 つの数、釣れる最大の魚の数。
入出力例#
入力例 #1：
2
1
10 1
2 5
2
出力例 #1：
31
説明#
1 <= H <= 16
2 <= n <= 25
考え方#
まず、perisno さんに感謝します。
停止する池を列挙し、ここまでの時間tm[i]を計算します（入力時に累積和にします）。
釣りの時間は(h-tm[i])です。
最初のiつの池で釣れる魚をpriority_queueにpushします。
終了時間までに現在の最大の魚を釣り、減らす量を引いてから再びpushします。
これにより、各池で釣るべき最適な時間が求められます。
答えは各池での最適解の最大値です。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1e5+5;
struct pond{
int sl,jian;
friend bool operator <(pond a,pond b){
return a.sl<b.sl;
}
} a[MAXN];
int tm[MAXN];
int n,h;
priority_queue<pond> q;
int main(){
cin>>n>>h;
h*=12;
for(int i=1;i<=n;++i){
cin>>a[i].sl;
}
for(int i=1;i<=n;++i){
cin>>a[i].jian;
}
for(int i=1;i<n;++i){
cin>>tm[i+1];
tm[i+1]+=tm[i];
}
int ans=0;
for(int i=1;i<=n&&h-tm[i]>0;++i){
int cnt=0;
int ti=h-tm[i];
for(int j=1;j<=i;++j){
q.push(a[j]);
}
while(!q.empty()&&ti){
pond u=q.top();
q.pop();
cnt+=u.sl;
u.sl-=u.jian;
if(u.sl>0)q.push(u);
--ti;
}
ans=max(ans,cnt);
}
cout<<ans<<endl;
return 0;
}