//Semiexpress
#include <iostream>
#include <queue>
#include <map>
#define MIN(a, b) ((a<b)? a :b )
#define MAX(a, b) ((a>b)? a :b )
long long n, m, k, a, b, c, t, sum, add, num_station;
long long eff_left_b, new_eff_left, local_adv, semi_adv;
long long pos, new_add;
long long arr[200007];
std::map<long long, long long> effort;
std::map<long long, long long> next_station;
std::priority_queue<std::pair<long long, int>> que;
std::pair<long long, int> pa;
int main(){
std::cin.tie(0);
std::ios_base::sync_with_stdio(0);
std::cin >> n >> m >> k;
std::cin >> a >> b >> c;
std::cin >> t;
sum = 0;
for(int i = 0; i<m; ++i){
std::cin >> arr[i];
--arr[i];
}
sum=-1;
for(int i = 0; (i<m-1)&&(arr[i]*b<=t); ++i){
eff_left_b=t-arr[i]*b;
local_adv=eff_left_b/a;
add=MIN(arr[i]+local_adv, arr[i+1]-1);
add+=-arr[i]+1;
sum+=add;
if(arr[i]+local_adv+1<arr[i+1]){
new_eff_left=(eff_left_b-(local_adv+1)*c);
if(new_eff_left<0){
continue;
}
semi_adv=new_eff_left/a+1;
add=MIN(arr[i]+local_adv+semi_adv ,arr[i+1]-1);
add-=arr[i]+local_adv;
que.push({add, arr[i]+local_adv+1});
effort[arr[i]+local_adv+1]=new_eff_left;
next_station[arr[i]+local_adv+1]=arr[i+1];
///how many more could i get, arr[i]+cat
//std::cout <<arr[i]+local_adv+1 <<"pos ";
//std::cout <<add <<"add ";
//std::cout <<new_eff_left <<"new effort left\n";
}
}
if(arr[m-1]*b<=t){
++sum;
}
num_station=m;
while(!que.empty()){
if(num_station==k){
break;
}
++num_station;
pa=que.top();
que.pop();
add=pa.first;
pos=pa.second;
sum+=add;
///Calculate the future
if(pos+add>=next_station[pos]){
continue;
}
new_eff_left=effort[pos]-add*c;
if(new_eff_left<0){
//std::cout << pos << "pos while eff<0\n";
continue;
}
semi_adv=new_eff_left/a+1;
new_add=MIN(pos+add-1+semi_adv ,next_station[pos]-1);
new_add-=pos+add-1;
que.push({new_add, pos+add});
effort[pos+add]=new_eff_left;
next_station[pos+add]=next_station[pos];
///how many more could i get, arr[i]+cat
//std::cout <<pos+add <<"pos ";
//std::cout <<new_add <<"add ";
//std::cout <<new_eff_left <<"new effort left\n";
}
if(sum<0){
sum=0;
}
std::cout << sum;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |