oj.uz

Submission #27464

# Submission time Handle Problem Language Result Execution time Memory
27464 2017-07-13T05:37:50 Z 김동현(#1155) Long Distance Coach (JOI17_coach) C++14
0 / 100
 0 ms 17648 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef pair<ll, ll> pll;

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

struct CHT{
	struct Lin{ lll a, b; };
	long double cr(Lin p, Lin q){ return 1L * (q.b - p.b) / (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], 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]) + (lll(k[i]) - i * lll(m[i])) * w - c[i]);
		C.upd(i * w, dp[i] + c[i] - lll(k[i]) * w);
	}
	printf("%lld\n", ll(lll(k[n]) * w - dp[n]));
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:34: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:37: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:41: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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17648 KB Output is correct
2 Correct 0 ms 17648 KB Output is correct
3 Correct 0 ms 17648 KB Output is correct
4 Correct 0 ms 17648 KB Output is correct
5 Correct 0 ms 17648 KB Output is correct
6 Incorrect 0 ms 17648 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17648 KB Output is correct
2 Correct 0 ms 17648 KB Output is correct
3 Correct 0 ms 17648 KB Output is correct
4 Correct 0 ms 17648 KB Output is correct
5 Correct 0 ms 17648 KB Output is correct
6 Incorrect 0 ms 17648 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17648 KB Output is correct
2 Correct 0 ms 17648 KB Output is correct
3 Correct 0 ms 17648 KB Output is correct
4 Correct 0 ms 17648 KB Output is correct
5 Correct 0 ms 17648 KB Output is correct
6 Incorrect 0 ms 17648 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17648 KB Output is correct
2 Correct 0 ms 17648 KB Output is correct
3 Correct 0 ms 17648 KB Output is correct
4 Correct 0 ms 17648 KB Output is correct
5 Correct 0 ms 17648 KB Output is correct
6 Incorrect 0 ms 17648 KB Output isn't correct
7 Halted 0 ms 0 KB -