oj.uz

Submission #478037

# Submission time Handle Problem Language Result Execution time Memory
478037 2021-10-05T08:51:16 Z pure_mem Long Distance Coach (JOI17_coach) C++14
0 / 100
 1 ms 336 KB 
#include <bits/stdc++.h>

#define X first
#define Y second
#define ll long long 
#define MP make_pair

using namespace std;

const int MAXN = 2e5 + 5;
const ll INF = 1e18;

struct Line {
	ll k, b;
	mutable function<const Line* ()> getNext;
	ll get(ll x) {
		return k * x + b;
	}
	double inters(const Line& oth) const {
		return (b - oth.b) * 1.0 / (oth.k - k);
	}
	bool operator< (const Line& oth) const {
		if(oth.k != INF) return k > oth.k;
		const Line* nxt = getNext();
		if(nxt == 0) return 0;
		return b - nxt->b >= (nxt->k - k) * oth.b;
	}
};

struct CHT: public multiset<Line> {
	bool bad(iterator y) {
		auto z = next(y);
		if(y == begin()) {
			if(z == end()) return 0;
			return y->k == z->k && y->b >= z->b;
		}
		auto x = prev(y);
		if (z == end()) return y->k == x->k && y->b >= x->b;
		return x->inters(*y) >= x->inters(*z);
	}
	void add(ll k, ll b) {
		auto it = insert((Line){k, b});
		it->getNext = [=] { return next(it) == end() ? 0 : &*next(it); };
		if(bad(it)) return void(erase(it));
		while(next(it) != end() && bad(next(it))) erase(next(it));
		while(it != begin() && bad(prev(it))) erase(prev(it));
	}
	ll get(ll x) {
		Line me = *lower_bound((Line){INF, x});
		return me.get(x);
	}
}cht;

int n, m;
ll len, w, t, water[MAXN], dp[MAXN], pr[MAXN];
pair<ll, ll> men[MAXN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> len >> n >> m >> w >> t;

	for(int i = 1;i <= n;i++)
		cin >> water[i];
	water[++n] = len;
	sort(water + 1, water + n + 1, [](ll a, ll b) {return a % t < b % t;});
	for(int i = 1;i <= m;i++)
		cin >> men[i].X >> men[i].Y;
	sort(men + 1, men + m + 1);
	for(int i = m;i >= 1;i--)
		pr[i] = pr[i + 1] + men[i].Y;
	for(int p1 = n, p2 = m;p2;p2--) {
		while(p1 && water[p1] % t > men[p2].X) {
			ll cost = water[p1] / t * w;
			cht.add(-cost, dp[p2 + 1] - pr[p2 + 1] + (p2 + 1) * cost);
			p1--;
		}
		dp[p2] = dp[p2 + 1] + (len - men[p2].X) / t * w + w;
		if(!cht.empty())
			dp[p2] = min(dp[p2], cht.get(p2) + pr[p2]);
		//cerr << p2 << " " << dp[p2] << "\n";
	}
	cout << dp[1] + len / t * w + w;
	return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 0 ms 324 KB Output is correct
15 Correct 0 ms 336 KB Output is correct
16 Correct 0 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 0 ms 336 KB Output is correct
20 Correct 0 ms 336 KB Output is correct
21 Incorrect 0 ms 328 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 0 ms 324 KB Output is correct
15 Correct 0 ms 336 KB Output is correct
16 Correct 0 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 0 ms 336 KB Output is correct
20 Correct 0 ms 336 KB Output is correct
21 Incorrect 0 ms 328 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 0 ms 324 KB Output is correct
15 Correct 0 ms 336 KB Output is correct
16 Correct 0 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 0 ms 336 KB Output is correct
20 Correct 0 ms 336 KB Output is correct
21 Incorrect 0 ms 328 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 0 ms 324 KB Output is correct
15 Correct 0 ms 336 KB Output is correct
16 Correct 0 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 0 ms 336 KB Output is correct
20 Correct 0 ms 336 KB Output is correct
21 Incorrect 0 ms 328 KB Output isn't correct
22 Halted 0 ms 0 KB -