#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll lim=1e12;
const ll inf=1e18;
struct Line{
ll k,n;
Line(){}
Line(ll a,ll b):k(a),n(b){}
__int128 Get1(ll x){return __int128(x)*__int128(k)+__int128(n);}
ll Get(ll x){return x*k+n;}
};
const int N=200050;
int ls[N],rs[N],tsz,root;
Line line[N];
void AddLine(int&c,ll ss,ll se,Line k){
if(!c){c=++tsz;line[c]=k;return;}
__int128 A=line[c].Get1(ss),B=k.Get1(ss),C=line[c].Get1(se),D=k.Get1(se);
if(A<=B&&C<=D)return;
if(A>=B&&C>=D){line[c]=k;return;}
ll mid=ss+se>>1;
if(A>B)swap(line[c],k);
if(line[c].Get(mid)<=k.Get(mid))AddLine(rs[c],mid+1,se,k);
else swap(k,line[c]),AddLine(ls[c],ss,mid,k);
}
ll Get(int c,ll ss,ll se,ll qi){
if(!c)return inf;
ll ans=line[c].Get(qi);
if(ss==se)return ans;
ll mid=ss+se>>1;
if(qi<=mid)return min(ans,Get(ls[c],ss,mid,qi));
else return min(ans,Get(rs[c],mid+1,se,qi));
}
ll s[N],mn[N],dp[N],pre[N];
pair<ll,ll> a[N];
int main(){
int n,m;ll x,t,w;
scanf("%lld %i %i %lld %lld",&x,&n,&m,&w,&t);
for(int i=1;i<=n;i++)scanf("%lld",&s[i]);s[++n]=x;
for(int i=1;i<=m;i++)scanf("%lld %lld",&a[i].first,&a[i].second),mn[i]=inf;
sort(a+1,a+1+m);
for(int i=1;i<=m;i++)pre[i]=pre[i-1]+a[i].second;
for(int i=1;i<=n;i++){
int j=upper_bound(a+1,a+1+m,(pair<ll,ll>){s[i]%t,inf})-a-1;
mn[j]=min(mn[j],s[i]/t);
}
dp[0]=(x/t+1)*w;
AddLine(root,0,lim,Line(0,dp[0]));
for(int i=1;i<=m;i++){
dp[i]=dp[i-1]+((x-a[i].first)/t+1)*w;
if(mn[i]!=inf)dp[i]=min(dp[i],Get(root,0,lim,mn[i])+mn[i]*i*w+pre[i]);
AddLine(root,0,lim,Line(-i*w,dp[i]-pre[i]));
}
printf("%lld\n",round(dp[m]));
return 0;
}
Compilation message
coach.cpp: In function 'void AddLine(int&, long long int, long long int, Line)':
coach.cpp:21:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | ll mid=ss+se>>1;
| ~~^~~
coach.cpp: In function 'long long int Get(int, long long int, long long int, long long int)':
coach.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | ll mid=ss+se>>1;
| ~~^~~
coach.cpp: In function 'int main()':
coach.cpp:39:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
39 | for(int i=1;i<=n;i++)scanf("%lld",&s[i]);s[++n]=x;
| ^~~
coach.cpp:39:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
39 | for(int i=1;i<=n;i++)scanf("%lld",&s[i]);s[++n]=x;
| ^
coach.cpp:54:13: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} [-Wformat=]
54 | printf("%lld\n",round(dp[m]));
| ~~~^ ~~~~~~~~~~~~
| | |
| | __gnu_cxx::__enable_if<true, double>::__type {aka double}
| long long int
| %f
coach.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
38 | scanf("%lld %i %i %lld %lld",&x,&n,&m,&w,&t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:39:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
39 | for(int i=1;i<=n;i++)scanf("%lld",&s[i]);s[++n]=x;
| ~~~~~^~~~~~~~~~~~~~
coach.cpp:40:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
40 | for(int i=1;i<=m;i++)scanf("%lld %lld",&a[i].first,&a[i].second),mn[i]=inf;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
