oj.uz

답안 #27463

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27463 2017-07-13T05:30:40 Z 김동현(#1155) Long Distance Coach (JOI17_coach) C++14
46 / 100
 0 ms 16088 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

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

struct CHT{
	struct Lin{ ll 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(ll a, ll 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++;
	}
	ll get(ll 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]) + (k[i] - i * m[i]) * w - c[i]);
		C.upd(i * w, dp[i] + c[i] - k[i] * w);
	}
	printf("%lld\n", k[n] * w - dp[n]);
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:32: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:35: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:39: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.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 16088 KB Output is correct
2 Correct 0 ms 16088 KB Output is correct
3 Correct 0 ms 16088 KB Output is correct
4 Correct 0 ms 16088 KB Output is correct
5 Correct 0 ms 16088 KB Output is correct
6 Correct 0 ms 16088 KB Output is correct
7 Correct 0 ms 16088 KB Output is correct
8 Correct 0 ms 16088 KB Output is correct
9 Correct 0 ms 16088 KB Output is correct
10 Correct 0 ms 16088 KB Output is correct
11 Correct 0 ms 16088 KB Output is correct
12 Correct 0 ms 16088 KB Output is correct
13 Correct 0 ms 16088 KB Output is correct
14 Correct 0 ms 16088 KB Output is correct
15 Correct 0 ms 16088 KB Output is correct
16 Correct 0 ms 16088 KB Output is correct
17 Correct 0 ms 16088 KB Output is correct
18 Correct 0 ms 16088 KB Output is correct
19 Correct 0 ms 16088 KB Output is correct
20 Correct 0 ms 16088 KB Output is correct
21 Correct 0 ms 16088 KB Output is correct
22 Correct 0 ms 16088 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 16088 KB Output is correct
2 Correct 0 ms 16088 KB Output is correct
3 Correct 0 ms 16088 KB Output is correct
4 Correct 0 ms 16088 KB Output is correct
5 Correct 0 ms 16088 KB Output is correct
6 Correct 0 ms 16088 KB Output is correct
7 Correct 0 ms 16088 KB Output is correct
8 Correct 0 ms 16088 KB Output is correct
9 Correct 0 ms 16088 KB Output is correct
10 Correct 0 ms 16088 KB Output is correct
11 Correct 0 ms 16088 KB Output is correct
12 Correct 0 ms 16088 KB Output is correct
13 Correct 0 ms 16088 KB Output is correct
14 Correct 0 ms 16088 KB Output is correct
15 Correct 0 ms 16088 KB Output is correct
16 Correct 0 ms 16088 KB Output is correct
17 Correct 0 ms 16088 KB Output is correct
18 Correct 0 ms 16088 KB Output is correct
19 Correct 0 ms 16088 KB Output is correct
20 Correct 0 ms 16088 KB Output is correct
21 Correct 0 ms 16088 KB Output is correct
22 Correct 0 ms 16088 KB Output is correct
23 Correct 0 ms 16088 KB Output is correct
24 Correct 0 ms 16088 KB Output is correct
25 Correct 0 ms 16088 KB Output is correct
26 Correct 0 ms 16088 KB Output is correct
27 Correct 0 ms 16088 KB Output is correct
28 Correct 0 ms 16088 KB Output is correct
29 Correct 0 ms 16088 KB Output is correct
30 Correct 0 ms 16088 KB Output is correct
31 Correct 0 ms 16088 KB Output is correct
32 Correct 0 ms 16088 KB Output is correct
33 Correct 0 ms 16088 KB Output is correct
34 Correct 0 ms 16088 KB Output is correct
35 Correct 0 ms 16088 KB Output is correct
36 Correct 0 ms 16088 KB Output is correct
37 Correct 0 ms 16088 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 16088 KB Output is correct
2 Correct 0 ms 16088 KB Output is correct
3 Correct 0 ms 16088 KB Output is correct
4 Correct 0 ms 16088 KB Output is correct
5 Correct 0 ms 16088 KB Output is correct
6 Correct 0 ms 16088 KB Output is correct
7 Correct 0 ms 16088 KB Output is correct
8 Correct 0 ms 16088 KB Output is correct
9 Correct 0 ms 16088 KB Output is correct
10 Correct 0 ms 16088 KB Output is correct
11 Correct 0 ms 16088 KB Output is correct
12 Correct 0 ms 16088 KB Output is correct
13 Correct 0 ms 16088 KB Output is correct
14 Correct 0 ms 16088 KB Output is correct
15 Correct 0 ms 16088 KB Output is correct
16 Correct 0 ms 16088 KB Output is correct
17 Correct 0 ms 16088 KB Output is correct
18 Correct 0 ms 16088 KB Output is correct
19 Correct 0 ms 16088 KB Output is correct
20 Correct 0 ms 16088 KB Output is correct
21 Correct 0 ms 16088 KB Output is correct
22 Correct 0 ms 16088 KB Output is correct
23 Correct 0 ms 16088 KB Output is correct
24 Correct 0 ms 16088 KB Output is correct
25 Correct 0 ms 16088 KB Output is correct
26 Correct 0 ms 16088 KB Output is correct
27 Correct 0 ms 16088 KB Output is correct
28 Correct 0 ms 16088 KB Output is correct
29 Correct 0 ms 16088 KB Output is correct
30 Correct 0 ms 16088 KB Output is correct
31 Correct 0 ms 16088 KB Output is correct
32 Correct 0 ms 16088 KB Output is correct
33 Correct 0 ms 16088 KB Output is correct
34 Correct 0 ms 16088 KB Output is correct
35 Correct 0 ms 16088 KB Output is correct
36 Correct 0 ms 16088 KB Output is correct
37 Correct 0 ms 16088 KB Output is correct
38 Incorrect 0 ms 16088 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 16088 KB Output is correct
2 Correct 0 ms 16088 KB Output is correct
3 Correct 0 ms 16088 KB Output is correct
4 Correct 0 ms 16088 KB Output is correct
5 Correct 0 ms 16088 KB Output is correct
6 Correct 0 ms 16088 KB Output is correct
7 Correct 0 ms 16088 KB Output is correct
8 Correct 0 ms 16088 KB Output is correct
9 Correct 0 ms 16088 KB Output is correct
10 Correct 0 ms 16088 KB Output is correct
11 Correct 0 ms 16088 KB Output is correct
12 Correct 0 ms 16088 KB Output is correct
13 Correct 0 ms 16088 KB Output is correct
14 Correct 0 ms 16088 KB Output is correct
15 Correct 0 ms 16088 KB Output is correct
16 Correct 0 ms 16088 KB Output is correct
17 Correct 0 ms 16088 KB Output is correct
18 Correct 0 ms 16088 KB Output is correct
19 Correct 0 ms 16088 KB Output is correct
20 Correct 0 ms 16088 KB Output is correct
21 Correct 0 ms 16088 KB Output is correct
22 Correct 0 ms 16088 KB Output is correct
23 Correct 0 ms 16088 KB Output is correct
24 Correct 0 ms 16088 KB Output is correct
25 Correct 0 ms 16088 KB Output is correct
26 Correct 0 ms 16088 KB Output is correct
27 Correct 0 ms 16088 KB Output is correct
28 Correct 0 ms 16088 KB Output is correct
29 Correct 0 ms 16088 KB Output is correct
30 Correct 0 ms 16088 KB Output is correct
31 Correct 0 ms 16088 KB Output is correct
32 Correct 0 ms 16088 KB Output is correct
33 Correct 0 ms 16088 KB Output is correct
34 Correct 0 ms 16088 KB Output is correct
35 Correct 0 ms 16088 KB Output is correct
36 Correct 0 ms 16088 KB Output is correct
37 Correct 0 ms 16088 KB Output is correct
38 Incorrect 0 ms 16088 KB Output isn't correct
39 Halted 0 ms 0 KB -