#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
{
i64 a ;
i64 b;
Line(i64 a , i64 b) : a(a) , b(b) {};
};
struct Hull
{
Line X ;
long double intersec;
};
class Convexhull
{
public:
vector<Hull> line;
double getintersec(Line x , Line y)
{
return (long double)(y.b - x.b) / (x.a - y.a);
}
i64 f(Line a , i64 x)
{
return a.a * x + a.b;
}
void addline(Line x)
{
int n = line.size();
while (n > 1 && getintersec(x , line[n - 2].X) <= line[n - 1].intersec)
{
--n;
line.pop_back();
}
if (line.empty()) line.push_back({x , LLONG_MIN});
else line.push_back({x , getintersec(x , line[n - 1].X)});
return;
}
i64 find(i64 val)
{
int l = 0 , r = line.size()-1 , pos = 0;
while (l<=r)
{
int m = l + r >> 1;
if (line[m].intersec <= val)
pos = m , l = m + 1;
else r = m - 1;
}
return f(line[pos].X , val);
}
void add(i64 a , i64 b)
{
addline(Line{a,b});
return;
}
void reset()
{
line.clear();
}
};
}
namespace subtask2{
bool check(){
return n<=2e5;
}
using namespace Convex_hull;
Convexhull 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.add(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.add(-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:150:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
coach.cpp:151:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
151 | 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... |