Submission #27472

#	Time	Username	Problem	Language	Result	Execution time	Memory
27472		kdh9949	Long Distance Coach (JOI17_coach)	C++14	100 / 100	253 ms	36272 KiB

coach

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;

int q, n;
ll x, t, w;
lll dp[200010], m[200010], k[200010], d[200010], c[200010];
pll a[200010], b[200010];

struct CHT{
	struct Lin{ lll a, b; };
	ld cr(Lin p, Lin q){ return ld(q.b - p.b) / ld(p.a - q.a); }
	vector<Lin> v;
	int r;
	void upd(lll a, lll b){
		Lin c = {a, b};
		while(r > 1 && cr(v[r - 2], v[r - 1]) > cr(v[r - 2], c)){ v.pop_back(); r--; }
		v.push_back(c); r++;
	}
	lll get(lll x){
		int s = 0, e = r - 2;
		while(s <= e){
			int m = (s + e) / 2;
			if(cr(v[m], v[m + 1]) <= x) s = m + 1;
			else e = m - 1;
		}
		return v[s].a * x + v[s].b;
	}
} C;

int main(){
	scanf("%lld%d%d%lld%lld", &x, &q, &n, &w, &t);
	b[0] = {x % t, x / t};
	for(int i = 1; i <= q; i++){
		ll x; scanf("%lld", &x);
		b[i] = {x % t, x / t};
	}
	for(int i = 1; i <= n; i++){
		scanf("%lld%lld", &a[i].first, &a[i].second);
	}
	sort(a + 1, a + n + 1);
	k[0] = (x + t - 1) / t;
	for(int i = 1; i <= n; i++){
		c[i] = c[i - 1] + a[i].second;
		k[i] = k[i - 1] + x / t + (a[i].first < x % t);
	}
	fill(m + 1, m + n + 1, (x + t - 1) / t + 1);
	for(int i = 0; i <= q; i++){
		int t = int(upper_bound(a + 1, a + n + 1, b[i]) - a - 1);
		m[t] = min(m[t], lll(b[i].second));
	}
	C.upd(0, -k[0] * w);
	for(int i = 1; i <= n; i++){
		dp[i] = max(dp[i - 1], C.get(m[i]) + (k[i] - i * m[i]) * w - c[i]);
		C.upd(i * w, dp[i] + c[i] - k[i] * w);
	}
	printf("%lld\n", ll(k[n] * w - dp[n]));
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:35:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%d%d%lld%lld", &x, &q, &n, &w, &t);
                                               ^
coach.cpp:38:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll x; scanf("%lld", &x);
                          ^
coach.cpp:42:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &a[i].first, &a[i].second);
                                               ^

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