Submission #27680

#	Time	Username	Problem	Language	Result	Execution time	Memory
27680		suhgyuho_william	Long Distance Coach (JOI17_coach)	C++14	100 / 100	229 ms	14524 KiB

coach

#include <bits/stdc++.h>

#define lld long long
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007

using namespace std;

int N,M;
lld X,W,T;
lld a[200002],d[200002],memo[200002],sum[200002];
struct data{
	lld d,c;
	data(){}
	data(lld d,lld c):d(d),c(c){}
	bool operator < (const data &cmp) const{
		return d < cmp.d;
	}
}b[200002];

pll tmp[200002];
struct CHTaaa{
	int cr = -1;
	lld f(int num,lld x){
		return tmp[num].first*x+tmp[num].second;
	}
	lld ccw(pll x,pll y,pll z){
		return (x.first*y.second+y.first*z.second+z.first*x.second)
			-(y.first*x.second+z.first*y.second+x.first*z.second);
	}
	void add(lld x,lld y){
		while(cr > 0 && ccw(tmp[cr-1],tmp[cr],pll(x,y)) >= 0) cr--;
		cr++;
		tmp[cr] = pll(x,y);
	}
	lld get(lld x){
		int l,r;
		l = 0; r = cr;
		while(l < r){
			int m = (l+r)>>1;
			if(f(m,x) < f(m+1,x)) r = m;
			else l = m+1;
		}
		return f(l,x);
	}
}cht;

lld get(lld x){
	return ((X-x)/T+1)*W;
}

int main(){
	long long iX,iW,iT;
	scanf("%lld %d %d %lld %lld",&iX,&N,&M,&iW,&iT);
	X = iX; W = iW; T = iT;
	for(int i=1; i<=N; i++){
		long long ia;
		scanf("%lld",&ia);
		a[i] = ia;
	}
	sort(a+1,a+N+1);
	for(int i=1; i<=M; i++){
		long long id,ic;
		scanf("%lld %lld",&id,&ic);
		b[i].d = id; b[i].c = ic;
	}
	sort(b+1,b+M+1);
	a[N+1] = X;
	for(int i=1; i<=M; i++){
		memo[i] = Linf;
		sum[i] = sum[i-1]+b[i].c;
	}
	for(int i=1; i<=N+1; i++){
		int it;
		it = lower_bound(b+1,b+M+1,data(a[i]%T,0))-b-1;
		memo[it] = min(memo[it],(a[i]/T)*W);
	}
	
	d[0] = get(0);
	cht.add(0,d[0]);
	for(int i=1; i<=M; i++){
		d[i] = Linf;
		if(memo[i] != Linf){
			d[i] = cht.get(memo[i]);
			d[i] += sum[i]+memo[i]*i;
		}
		d[i] = min(d[i],d[i-1]+get(b[i].d));
		cht.add(-i,d[i]-sum[i]);
	}
	long long print = d[M];
	printf("%lld\n",print);

	return 0;
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:59:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %d %d %lld %lld",&iX,&N,&M,&iW,&iT);
                                                 ^
coach.cpp:63:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&ia);
                    ^
coach.cpp:69:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&id,&ic);
                             ^

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