#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define i64 long long
const int N=(int)2e5;
const LL INF=(LL)1e18;
LL s[N+2];
pair<LL,int>d[N+2];
int n,m;
LL w,x,t;
namespace subtask1{
bool check(){
return n<=1000 && m<=1000;
}
LL pre[N+2]={};
int need[N+2]={};
LL dp[N+2]={};
void main_code(){
sort(d+1,d+m+1,[&](pair<LL,int> x,pair<LL,int> y){
return x.first % t < y.first % t;
});
s[++n]=x;
sort(s+1,s+n+1);
for(int i=1;i<=m;++i) pre[i]=pre[i-1]+d[i].second;
for(int i=1;i<=n;++i) {
int pos=upper_bound(d+1,d+m+1,pair<LL,int>(s[i]%t,-1))-d-1;
if (need[pos]==0) need[pos]=i;
}
dp[0]=(LL)(x/t)*w+w;
for(int i=1;i<=m;++i){
dp[i]=dp[i-1]+(LL)(x/t+(x%t>=d[i].first))*w;
if (need[i]){
for(int j=0;j<i;++j){
LL t1=(s[need[i]]/t);
LL addmore=pre[i]+w*i*t1+dp[j]-pre[j]-t1*j*w;
dp[i]=min(dp[i],addmore);
}
}
}
cout<<dp[m]<<'\n';
}
}
namespace Convex_hull{
struct Line{
LL a,b;
Line() {};
Line(LL a,LL b) : a(a),b(b) {};
};
struct Hull{
Line x;
long double intersec;
};
long double get_intersec(Line x,Line y){
return (long double)(y.b-x.b)/(x.a-y.a);
}
class Convex{
public:
vector<Hull>line;
LL F(Line a,LL x){
return a.a*x+a.b;
}
void add_line(Line x){
int n=line.size();
while (n>1 && line.back().intersec >= get_intersec(x,line[n-2].x)) {
line.pop_back(),--n;
}
if (line.empty()) line.push_back({x,LLONG_MIN});
else line.push_back({x,get_intersec(line[n-1].x,x)});
return;
}
LL Find(LL x){
int low=0,high=line.size()-1,pos=0;
while (low<=high){
int mid=(low+high)/2;
if (line[mid].intersec <= x){
pos=mid;
low=mid+1;
}
else high=mid-1;
}
return F(line[pos].x,x);
}
void insert(LL a,LL b){
add_line(Line(a,b));
return;
}
};
}
namespace subtask2{
bool check(){
return n<=2e5;
}
using namespace Convex_hull;
Convex baoloi;
LL pre[N+2]={};
LL dp[N+2]={};
int need[N+2]={};
void main_code(){
sort(d+1,d+m+1);
s[++n]=x;
sort(s+1,s+n+1);
for(int i=1;i<=m;++i) pre[i]=pre[i-1]+d[i].second;
for(int i=1;i<=n;++i) {
int pos=upper_bound(d+1,d+m+1,pair<LL,int>(s[i]%t,-1))-d-1;
if (need[pos]==0) need[pos]=i;
}
dp[0]=(LL)(x/t)*w+w;
baoloi.insert(0,dp[0]-pre[0]);
for(int i=1;i<=m;++i){
dp[i]=dp[i-1]+w*((x/t)+(x%t>=d[i].first));
if (need[i]){
LL t1=w*(s[need[i]]/t);
LL addmore=pre[i]+t1*i+baoloi.Find(t1);
dp[i]=min(dp[i],addmore);
}
baoloi.insert(-i,dp[i]-pre[i]);
}
cout<<dp[m];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0) ; cout.tie(0);
#define task "main"
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin>>x>>n>>m>>w>>t;
for(int i=1;i<=n;++i) cin>>s[i];
for(int i=1;i<=m;++i) cin>>d[i].first>>d[i].second;
if (subtask2::check()){
return subtask2::main_code(),0;
}
return 0;
}
Compilation message (stderr)
coach.cpp: In function 'int main()':
coach.cpp:138:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
coach.cpp:139:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
139 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |