QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85265 | #366. Long Distance Coach | lmeowdn | 0 | 5ms | 16128kb | C++14 | 1.8kb | 2023-03-07 14:31:44 | 2023-03-07 14:31:44 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
#define sgn(x) ((x)&1?-1:1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
return x*w;
}
const int N=1e6+9;
int X,n,m,w,a[N],T,s[N],t[N],g[N],st[N],top,f[N],c[N],y[N];
pii p[N];
bool cmpc(int a,int b,int c) {
return __int128(y[a]-y[b])*(b-c)<__int128(y[b]-y[c])*(a-b);
}
bool cmpk(int a,int b,int k) {
return y[a]-y[b]<k*(b-a);
}
signed main() {
X=read(), n=read(), m=read(), w=read(), T=read();
rep(i,1,n) s[i]=read(); s[++n]=X;
rep(i,1,m) p[i].fi=read(), p[i].se=read();
sort(p+1,p+m+1);
rep(i,1,m) c[i]=c[i-1]+p[i].se;
rep(i,1,m) a[i]=s[n]/T+(p[i].fi<=s[n]%T);
rep(i,1,m) t[i]=p[i].fi, g[i]=a[i];
rep(i,1,n) {
int p=lower_bound(t,t+m+1,s[i]%T)-t-1;
if(p) g[p]=min(g[p],s[i]/T);
}
f[0]=w*(s[n]/T+1), y[0]=f[0], st[++top]=0;
rep(i,1,m) {
f[i]=f[i-1]+a[i]*w;
int l=2,r=top,res=y[0];
while(l<=r) {
int mid=l+r>>1; res=min(res,y[st[mid]]-w*g[i]*st[mid]);
if(cmpk(st[mid-1],st[mid],w*g[i])) l=mid+1;
else r=mid-1;
}
f[i]=min(f[i],res+w*g[i]*i+c[i]);
y[i]=f[i]-c[i];
while(top>1&&!cmpc(st[top-1],st[top],i)) top--;
st[++top]=i;
}
printf("%lld\n",f[m]);
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: 0ms
memory: 15872kb
input:
999999999999 1 1 1000000 4 1 2 3
output:
499999999999000003
result:
ok single line: '499999999999000003'
Test #2:
score: 0
Accepted
time: 1ms
memory: 16036kb
input:
5 1 1 15 4 2 3 4
output:
45
result:
ok single line: '45'
Test #3:
score: 0
Accepted
time: 1ms
memory: 15896kb
input:
5 1 1 15 4 3 2 13
output:
43
result:
ok single line: '43'
Test #4:
score: 0
Accepted
time: 5ms
memory: 15868kb
input:
5 1 1 15 4 3 2 19
output:
45
result:
ok single line: '45'
Test #5:
score: 0
Accepted
time: 1ms
memory: 15824kb
input:
142 4 7 10 13 67 44 86 141 3 1000000000 6 1000000000 9 1000000000 1 60 4 81 7 48 10 14
output:
878
result:
ok single line: '878'
Test #6:
score: 0
Accepted
time: 1ms
memory: 15760kb
input:
142 3 8 10 13 68 46 37 4 1000000000 8 1000000000 1 61 2 59 5 79 6 79 9 20 10 155
output:
982
result:
ok single line: '982'
Test #7:
score: 0
Accepted
time: 5ms
memory: 16128kb
input:
150 8 8 10 18 5 88 75 87 83 14 109 112 17 30 7 70 2 24 10 25 12 34 9 92 8 30 13 18
output:
463
result:
ok single line: '463'
Test #8:
score: -16
Wrong Answer
time: 2ms
memory: 15852kb
input:
10000000000 8 8 6 18 9547257284 4226673527 9454195771 9513946487 7287482436 6692534804 3951479147 8774939403 12 415893810 4 735304001 13 184845346 14 354080601 15 455062532 16 886416267 3 985580216 1 97417991
output:
18719063460
result:
wrong answer 1st lines differ - expected: '18443869092', found: '18719063460'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%