Submission #658810

#	Time	Username	Problem	Language	Result	Execution time	Memory
658810		rsjw	Long Distance Coach (JOI17_coach)	C++17	100 / 100	413 ms	12376 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) (long double)(B(k2)-B(k1))/(K(k1)-K(k2))
int h=0,top=1;//stack in fact 
int q[N];
int getmin(int x) {
	int l=0,r=top-2,mid;
	while(l<=r) {
		mid=(l+r)/2;
		if(itsec(q[mid],q[mid+1])>x) r=mid-1; else l=mid+1;
	}
	return q[r+1];
}
signed main() {
	int i,j=1,Mn;
	//freopen("1.in","r",stdin);
	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&&h<top) {
			int ans=1e16;
//			for(int k=0; k<i; k++) ans=min(ans,E(k,Mn));
//			assert(ans==E(getmin(Mn),Mn));
			ans=E(getmin(Mn),Mn);
			f[i]=min(E(getmin(Mn),Mn)+A[i].c+i*w*Mn,f[i]);
		}
		while(top-h>=2&&itsec(q[top-1],q[top-2])>=itsec(i,q[top-1])) top--;
		q[top++]=i;
	}
	cout<<f[m]+(x/t+1)*w<<endl;
	return 0;
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:44:8: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
   44 |    int ans=1e16;
      |        ^~~

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