Submission #563916

#	Time	Username	Problem	Language	Result	Execution time	Memory
563916		amunduzbaev	Long Distance Coach (JOI17_coach)	C++17	100 / 100	310 ms	208068 KiB

coach

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define double long double
#define int long long
 
const long long inf = 1e18;
const int N = 2e5 + 5;

struct node{
	int m, b, lx, rx;
	
	double operator * (node& x){
		return (x.b - b) * 1. / (m - x.m);
	}
	
	int cost(int x){
		return m * x + b;
	}
};

const long long M = 1e12 + 5;
int t, w;

struct LiChao{
	node tree[N * 30] {};
	int last;
	
	void init(){
		for(int i=0;i<N*30;i++) tree[i] = {w * t, inf, 0, 0};
		last = 0;
	}
	
	void make(int x){
		if(!tree[x].lx) tree[x].lx = ++last;
		if(!tree[x].rx) tree[x].rx = ++last;
	}

	void add(node v, int lx = 0, int rx = M, int x = 0){
		if(tree[x].m == v.m){
			tree[x].b = min(v.b, tree[x].b);
			return;
		}
		
		if(lx == rx){
			if(tree[x].cost(lx) > v.cost(lx)) swap(tree[x], v);
			return;
		}
		
		make(x);
		double in = tree[x] * v;
		int m = (lx + rx) >> 1;
		v.lx = tree[x].lx, v.rx = tree[x].rx;
		if(m < in){
			if(tree[x].cost(m) > v.cost(m)){
				swap(tree[x], v);
			}
			add(v, m + 1, rx, tree[x].rx);
		} else {
			if(tree[x].cost(m + 1) > v.cost(m + 1)){
				swap(tree[x], v);
			}
			add(v, lx, m, tree[x].lx);
		}
	}
	
	int get(int i, int lx = 0, int rx = M, int x = 0){
		if(lx == rx) return tree[x].cost(i);
		int m = (lx + rx) >> 1;
		make(x);
		if(i <= m) return min(get(i, lx, m, tree[x].lx), tree[x].cost(i));
		else return min(get(i, m+1, rx, tree[x].rx), tree[x].cost(i));
	}
}tree;

int s[N], d[N], c[N], pref[N], cnt[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int x, n, m; cin>>x>>n>>m>>w>>t;
	tree.init();
	for(int i=0;i<n;i++) cin>>s[i];
	vector<int> p(m), d_(m), mn(m, x + 1);
	int tot = 0;
	for(int i=0;i<m;i++){
		cin>>d[i]>>c[i];
		p[i] = i;
	}
	
	tot += (x / t + 1) * w;
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return d[i] < d[j];
	});
	for(int i=0;i<m;i++){
		d_[i] = d[p[i]];
		cnt[i] = x / t + (d_[i] < x % t);
		tot += cnt[i] * w;
		if(i) pref[i] += pref[i-1], cnt[i] += cnt[i-1];
		pref[i] += c[p[i]];
	}
	s[n] = x;
	for(int i=0;i<=n;i++){
		int j = upper_bound(d_.begin(), d_.end(), s[i] % t) - d_.begin();
		if(j){ --j;
			//~ assert(d_[j] != s[i] % t);
			mn[j] = min(mn[j], s[i]);
		}
	}
	
	//~ cout<<w<<"\n";
	//~ for(int i=0;i<m;i++){
		//~ cout<<-i * w<<" "<<cnt[i] * w - pref[i]<<"\n";
	//~ }
	
	vector<int> dp(m);
	int Mx = M / t + 5;
	tree.add({w, 0});
	for(int i=0;i<m;i++){
		if(i) dp[i] = dp[i-1];
		if(mn[i] > x){
			tree.add({-i * w, dp[i] + cnt[i] * w - pref[i]}, 0, Mx);
			continue;
		}
		int T = mn[i] / t;	
		dp[i] = min(dp[i], tree.get(T, 0, Mx) - cnt[i] * w + T * i * w + pref[i]);
		tree.add({-i * w, dp[i] + cnt[i] * w - pref[i]}, 0, Mx);
	}
	
	//~ for(int i=0;i<m;i++) cout<<dp[i]<<" ";
	//~ cout<<"\n";
	
	cout<<tot + dp[m-1]<<"\n";
}
 
/*

0 0 0 0 -23
0 0 0 0 -29

105 3 5 9 10
59
68
71
4 71
6 32
7 29
3 62
2 35

*/

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