Submission #27471

#	Time	Username	Problem	Language	Result	Execution time	Memory
27471		khsoo01	Long Distance Coach (JOI17_coach)	C++11	100 / 100	253 ms	25332 KiB

coach

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
const ll N = 200005, inf = 1e18;

ll x, n, m, w, t, rf[N];
ll sum[N], mn[N];
ld dt[N];
pll a[N];

struct cht {
	vector<pld> v;
	ld val (pld &A, ll &P) {return A.X*P+A.Y;}
	bool valid (pld &A, pld &B, pld &C) {
		return (B.Y-A.Y)*(A.X-C.X) < (C.Y-A.Y)*(A.X-B.X);
	}
	void upd (ld G, ld B) {
		pld T = pld(G, B);
		for(ll i=v.size();i-->1;) {
			if(valid(v[i-1], v[i], T)) break;
			else v.pop_back();
		}
		v.push_back(T);
	}
	ld get (ll P) {
		ll S = 0, E = (ll)v.size()-1;
		while(S<E) {
			ll T = (S+E)/2;
			val(v[T],P)<val(v[T+1],P) ? E = T : S = T+1;
		}
		return val(v[S], P);
	}
} h;

ll cost (ll P) {return (x/t+(x%t>=P))*w;}

int main()
{
	scanf("%lld%lld%lld%lld%lld",&x,&n,&m,&w,&t);
	for(ll i=1;i<=n;i++) scanf("%lld",&rf[i]);
	for(ll i=1;i<=m;i++) scanf("%lld%lld",&a[i].X,&a[i].Y);
	sort(a+1, a+1+m);
	for(ll i=1;i<=m;i++) {
		sum[i] = sum[i-1] + a[i].Y;
		mn[i] = inf;
	}
	rf[n+1] = x;
	for(ll i=1;i<=n+1;i++) {
		ll I = lower_bound(a+1, a+1+m, pll(rf[i]%t, 0)) - a - 1;
		mn[I] = min(mn[I], rf[i]/t);
	}
	dt[0] = cost(0); h.upd(0, dt[0]);
	for(ll i=1;i<=m;i++) {
		dt[i] = dt[i-1]+cost(a[i].X);
		if(mn[i] != inf) dt[i] = min(dt[i], h.get(mn[i])+mn[i]*i*w+sum[i]);
		h.upd(-i*w, dt[i]-sum[i]);
	}
	ll ans = dt[m];
	printf("%lld\n",(dt[m]-ans<0.5?ans:ans+1));
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:44:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld%lld",&x,&n,&m,&w,&t);
                                              ^
coach.cpp:45:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(ll i=1;i<=n;i++) scanf("%lld",&rf[i]);
                                           ^
coach.cpp:46:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(ll i=1;i<=m;i++) scanf("%lld%lld",&a[i].X,&a[i].Y);
                                                        ^

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