Submission #658801

#	Time	Username	Problem	Language	Result	Execution time	Memory
658801		rsjw	Long Distance Coach (JOI17_coach)	C++17	0 / 100	1 ms	468 KiB

coach

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200110;
int s[N],f[N];
struct passenger {
	int d,c;
	bool operator < (const passenger &ri) const {
		return d<ri.d;
	}
} A[N];
int x,n,m,w,t;
bool cmp(int a,int b) {
	return a%t<b%t;
}
#define K(p) (-p*w)
#define B(p) (f[p]-A[p].c)
#define E(p,x) (K(p)*(x)+B(p))
#define itsec(k1,k2) (double)(B(k2)-B(k1))/(K(k1)-K(k2))
int h=1,top=1;//stack in fact 
int q[N];
int getmin(int x) {
	int l=1,r=top,mid;
	while(l<=r) {
		mid=(l+r)/2;
		if(itsec(mid,mid+1)<=x) {
			l=mid+1;
		} else {
			r=mid-1;
		}
	}
	return l-1;
}
signed main() {
	int i,j=1,Mn;
	cin>>x>>n>>m>>w>>t;
	for(i=1; i<=n; i++) cin>>s[i];
	for(i=1; i<=m; i++) cin>>A[i].d>>A[i].c;
	A[m+1].d=t,f[0]=0,s[++n]=x;
	sort(s+1,s+n+1,cmp),sort(A+1,A+m+1);
	for(i=1; i<=m; i++) A[i].c+=A[i-1].c;
	while(s[j]%t<=A[1].d&&j<=n) j++;
	for(i=1; i<=m; i++) {
		for(Mn=1e16; j<=n&&s[j]%t<=A[i+1].d; j++) Mn=min(Mn,s[j]/t);
		f[i]=f[i-1]+((x-A[i].d)/t+1)*w;
		if(Mn!=1e16) {
			int ans=1e16;
			for(int k=0; k<i; k++) ans=min(ans,E(k,Mn));
			assert(ans==E(getmin(Mn),Mn));
			
			f[i]=min(ans+A[i].c+i*w*Mn,f[i]);
			while(top-h>=2&&itsec(top-1,top-2)>=itsec(i,top-1)) top--;
			q[top++]=i;
		}
	}
	cout<<f[m]+(x/t+1)*w<<endl;
	return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 30
• Subtask 3: 0 / 25
• Subtask 4: 0 / 29