Submission #127977

#	Time	Username	Problem	Language	Result	Execution time	Memory
127977		ainta	Long Distance Coach (JOI17_coach)	C++17	100 / 100	480 ms	38264 KiB

coach

#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<functional>
#include<set>
#define N_ 201000
using namespace std;
#define pii pair<int,int>
 
long long X[N_], D[N_];
int n, m;
long long cost, T;
 
struct point {
	long long x, c;
	bool operator <(const point &p)const {
		return x < p.x;
	}
}w[N_];
 
long long First[N_], Z[N_], INF = 4e18, D1[N_], D2[N_], SS[N_];
 
struct Seg {
	long long A, B;
};
 
vector<Seg>V;
 
void Put(long long A, long long B) {
	V.push_back({ A,B });
}
long long Get(long long x) {
	long long res = INF;
	for (auto &t : V) {
		res = min(res, t.A*x + t.B);
	}
	return res;
}
 
 
 
using line_t = long double;
const line_t is_query = -5e18;
struct Line {
	line_t m, b;
	mutable function<const Line*()> succ;
	bool operator<(const Line& rhs) const {
		if (rhs.b != is_query) return m < rhs.m;
		const Line* s = succ();
		if (!s) return 0;
		line_t x = rhs.m;
		return b - s->b < (s->m - m) * x;
	}
};
struct HullDynamic : public multiset<Line> { // will maintain upper hull for maximum
	bool bad(iterator y) {
		auto z = next(y);
		if (y == begin()) {
			if (z == end()) return 0;
			return y->m == z->m && y->b <= z->b;
		}
		auto x = prev(y);
		if (z == end()) return y->m == x->m && y->b <= x->b;
		return (x->b - y->b)*(z->m - y->m) >= (y->b - z->b)*(y->m - x->m);
	}
	void insert_line(line_t m, line_t b) {
		auto y = insert({ m, b });
		y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
		if (bad(y)) { erase(y); return; }
		while (next(y) != end() && bad(next(y))) erase(next(y));
		while (y != begin() && bad(prev(y))) erase(prev(y));
	}
	line_t query(line_t x) {
		Line p = { x,is_query };
		auto l = *lower_bound(p);
		return l.m * x + l.b;
	}
}H;
 
int main() {
	int i, j;
	scanf("%lld%d%d%lld%lld", &X[0], &m, &n, &cost, &T);
	for (i = 1; i <= m; i++) {
		scanf("%lld", &X[i]);
	}
	X[m + 1] = 0;
	sort(X, X + m + 2);
	m++;
	for (i = 1; i <= n; i++) {
		scanf("%lld%lld", &w[i].x, &w[i].c);
	}
	sort(w + 1, w + n + 1);
	for (i = 1; i <= n; i++) {
		Z[i] = w[i].x;
		SS[i] = SS[i - 1] + w[i].c;
	}
	D1[n + 1] = 0;
	D2[n + 1] = 0;
	for (i = 0; i <= n; i++) {
		D1[i] = INF;
		D2[i] = INF;
	}
	for (i = 0; i <= n; i++)First[i] = INF;
	for (i = 1; i <= m; i++) {
		int pv = lower_bound(Z, Z + n + 1, X[i] % T) - Z;
		First[pv % (n + 1)] = min(First[pv % (n + 1)], X[i]);
	}
 
	int ck = 0;
	for (i = n + 1; i >= 1; i--) {
		long long s = 0;
		D1[i - 1] = D2[i] + ((X[m] - w[i - 1].x) / T + 1)*cost;
		if (First[i % (n + 1)] < INF) {
			long long f = First[i % (n + 1)] / T * cost;
			//Put(-f, D2[i] + f * i + SS[i - 1]);
			H.insert_line(-(-f), -(D2[i] + f * i + SS[i - 1]));
			ck = 1;
		}
		if (i != 1) {
			D2[i - 1] = D1[i - 1];
			if (ck)D2[i - 1] = min(D2[i - 1], -(long long)H.query(i - 1) - SS[i - 2]);
		}
		//if (i != 1)D2[i - 1] = min(D1[i - 1], Get(i - 1) - SS[i - 2]);
	}
	printf("%lld\n", D1[0]);
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:112:13: warning: unused variable 's' [-Wunused-variable]
   long long s = 0;
             ^
coach.cpp:82:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
coach.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%d%d%lld%lld", &X[0], &m, &n, &cost, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &X[i]);
   ~~~~~^~~~~~~~~~~~~~~
coach.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &w[i].x, &w[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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