QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#97805 | #366. Long Distance Coach | tricyzhkx | 0 | 4ms | 23388kb | C++14 | 1.5kb | 2023-04-18 19:39:01 | 2023-04-18 19:39:02 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
ll pre[200010];
struct node
{
int typ;
ll r,w;
node(int _t=0,ll _r=0,ll _w=0):typ(_t),r(_r),w(_w){}
bool operator<(const node &a)const{return r<a.r;}
}a[400010];
struct Line
{
ll k,b;
Line(ll _k=0,ll _b=0):k(_k),b(_b){}
ll operator()(ll x)const{return k*x+b;}
}val[600010];
void update(int rt,int l,int r,Line F)
{
if(!val[rt].k) return val[rt]=F,void();
int mid=(l+r)/2;
if(F(mid)<val[rt](mid)) swap(val[rt],F);
if(l==r) return;
if(F(l)<val[rt](l)) update(rt*2,l,mid,F);
if(F(r)<val[rt](r)) update(rt*2+1,mid+1,r,F);
}
ll query(int rt,int l,int r,int x)
{
if(!val[rt].k) return INF;
ll ans=val[rt](x);
if(l==r) return ans;
int mid=(l+r)/2;
if(x<=mid) ans=min(ans,query(rt*2,l,mid,x));
else ans=min(ans,query(rt*2+1,mid+1,r,x));
return ans;
}
int main()
{
ll X,T,t,ans,minn=0;
int n,m,W,C,tot=0;
cin>>X>>n>>m>>W>>T;
for(int i=1;i<=n;i++) scanf("%lld",&t),a[++tot]=node(0,t%T,t/T*W);
a[++tot]=node(0,X%T,X/T*W);
ans=(X/T+1)*W;
for(int i=1;i<=m;i++)
{
scanf("%lld%d",&t,&C);
ans+=((X-t)/T+1)*W;
a[++tot]=node(1,t,C-((X-t)/T+1)*W);
}
sort(a+1,a+tot+1);
for(int i=1,j=0;i<=tot;i++)
if(a[i].typ) pre[j+1]=pre[j]+a[i].w,j++;
for(int i=tot,j=m;i>=1;i--)
if(a[i].typ) j--,minn=min(minn,query(1,0,m-1,j)-pre[j]);
else update(1,0,m-1,Line(-a[i].w,minn+pre[j]+j*a[i].w));
cout<<ans+minn<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 16
Accepted
time: 2ms
memory: 22096kb
input:
999999999999 1 1 1000000 4 1 2 3
output:
499999999999000003
result:
ok single line: '499999999999000003'
Test #2:
score: 0
Accepted
time: 1ms
memory: 23388kb
input:
5 1 1 15 4 2 3 4
output:
45
result:
ok single line: '45'
Test #3:
score: -16
Wrong Answer
time: 4ms
memory: 22256kb
input:
5 1 1 15 4 3 2 13
output:
45
result:
wrong answer 1st lines differ - expected: '43', found: '45'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%