oj.uz

Submission #1007912

# Submission time Handle Problem Language Result Execution time Memory
1007912 2024-06-25T18:50:44 Z beaboss Long Distance Coach (JOI17_coach) C++14
71 / 100
 2000 ms 21076 KB 
// Source: https://oj.uz/problem/view/JOI17_coach?locale=en
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;
#define int long long

typedef pair<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

const int INF = 2e18;

struct Line {
	int m, b;
	int evalX(int x) {
		return m * x + b;
	}
	double isectX(Line l) {
		return ((double) l.b - (double) b) / ((double) m - (double) l.m);
	}
};

deque<Line> line;
void add(Line l) {
	line.push_back(l);
	// while (line.size() > 0 && line[0].m == l.m) {
	// 	if (l.b < line[0].b) line.pop_front();
	// 	else return;
	// }
	// while (line.size() > 1 && line[0].isectX(line[1]) < l.isectX(line[1])) line.pop_front();
	// line.push_back(l);

}

int query(int pos) {
	int best = 0;

	for (auto val: line) best = min(best, val.evalX(pos));
	return best;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int x, n, m, w, t;
	cin >> x >> n >> m >> w >> t;
	m++;

	vector<array<int, 3> > all(n + m + 1, {-1, -1, 1});

	FOR(i, 1, n + 1) {
		cin >> all[i][1];
		all[i][0] = all[i][1] % t;
		all[i][2] = 0;
	}	
	FOR(i, n + 1, n + m) cin >> all[i][0] >> all[i][1];	
	all[n + m] = {x % t, x, 0};


	sort(all.begin(), all.end());

	vi prefc(n + m + 1, 0);
	vi cnt(n + m + 1, 0);
	for (int i = 1; i <= n + m; i++) {
		prefc[i] = prefc[i-1] + all[i][1] * all[i][2];
		cnt[i] = cnt[i-1] + all[i][2];
	}
	vi dp(n + m + 1, 0);
	int periods = (x / t);

	// add({0, 0});

	for (int i = 1; i <= n + m; i++) {
		// cout << all[i][0] << ' ' << all[i][1] << ' ' << all[i][2] << endl;
		if (all[i][2] == 0) { // refill point
			int skip = (all[i][1] - all[i][0]) / t;
			dp[i] = min(dp[i-1], query(-skip * w) + prefc[i] + skip * w * cnt[i]);
			// ckmin(dp[i], 0);
			// for (int j = 0; j < i; j++) {
			// 	int skip = (all[i][1] - all[i][0]) / t;
			// 	ckmin(dp[i], prefc[i] + skip * w * cnt[i] - skip * w * cnt[j] - prefc[j] + dp[j]);
			// }
		} else {
			dp[i] = dp[i-1] + w * (periods + (all[i][0] <= (x % t)));
		}

		add({cnt[i], -prefc[i] + dp[i]});


	}

	cout << dp[n + m] + (periods + 1ll) * w << endl;




}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 420 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 420 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 420 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 3 ms 604 KB Output is correct
39 Correct 3 ms 604 KB Output is correct
40 Correct 3 ms 660 KB Output is correct
41 Correct 4 ms 604 KB Output is correct
42 Correct 4 ms 604 KB Output is correct
43 Correct 3 ms 604 KB Output is correct
44 Correct 4 ms 604 KB Output is correct
45 Correct 3 ms 604 KB Output is correct
46 Correct 4 ms 604 KB Output is correct
47 Correct 3 ms 604 KB Output is correct
48 Correct 3 ms 604 KB Output is correct
49 Correct 3 ms 604 KB Output is correct
50 Correct 3 ms 604 KB Output is correct
51 Correct 3 ms 604 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 420 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 3 ms 604 KB Output is correct
39 Correct 3 ms 604 KB Output is correct
40 Correct 3 ms 660 KB Output is correct
41 Correct 4 ms 604 KB Output is correct
42 Correct 4 ms 604 KB Output is correct
43 Correct 3 ms 604 KB Output is correct
44 Correct 4 ms 604 KB Output is correct
45 Correct 3 ms 604 KB Output is correct
46 Correct 4 ms 604 KB Output is correct
47 Correct 3 ms 604 KB Output is correct
48 Correct 3 ms 604 KB Output is correct
49 Correct 3 ms 604 KB Output is correct
50 Correct 3 ms 604 KB Output is correct
51 Correct 3 ms 604 KB Output is correct
52 Execution timed out 2059 ms 21076 KB Time limit exceeded
53 Halted 0 ms 0 KB -