Problem Description#
Once upon a time, a game carefully designed by a child was mercilessly destroyed by the computer team. Feeling upset, VIP999 decided to treat him to a "Yearly Harvest" meal to console and encourage him. To show his sincerity, VIP999 also decided to go fishing himself.
However, because he still had to prepare for NOIP2013, Teacher Z only gave him H hours of free time. Assuming that there are N ponds along a horizontal road, numbered from 1 to N from left to right.
VIP999 is a child who values efficiency. He hopes to catch as many fish as possible in this time. He starts from pond 1 and walks to the right, choosing to stop and fish for a certain amount of time at some ponds. Finally, he ends his fishing at one of the ponds. He measured that it takes 5×Ti minutes to walk from pond i to pond i+1, and he also measured that he can catch Fi fish in the first 5 minutes of fishing at pond i, and the number of fish he can catch decreases by Di every 5 minutes thereafter. If the number of fish decreases to less than 0, it is considered 0. To simplify the problem, he assumes that no one else is fishing and there are no other factors that would affect the number of fish he can catch. Please write a program to find the maximum number of fish he can catch.
Input and Output Format#
Input format:
The first line: the number of ponds N.
The second line: the time H (in hours).
The third line: N numbers, f1, f2, ..., fn.
The fourth line: N numbers, d1, d2, ..., dn.
The fifth line: N-1 numbers, t1, t2, ..., tn-1.
Output format:
One number, the maximum number of fish that can be caught.
Input and Output Examples#
Input example #1:
2
1
10 1
2 5
2
Output example #1:
31
Explanation#
1 <= H <= 16
2 <= N <= 25
Approach#
First of all, thanks to perisno for the solution.
Enumerate the pond where the fishing stops, and calculate the time needed to walk from the beginning to this pond tm[i] (convert it to a prefix sum during input).
The time available for fishing is (h-tm[i]).
Push the fish that can be caught in the first i ponds into a priority_queue,
Pop out the pond that can catch the most fish at the current time before the time ends,
Subtract the required amount and push it back.
This way, the optimal fishing time for each pond can be calculated.
The answer is the maximum value of the optimal solution for each pond.
#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;
}