oj.uz

Submission #209159

# Submission time Handle Problem Language Result Execution time Memory
209159 2020-03-13T09:53:31 Z Siberian Semiexpress (JOI17_semiexpress) C++17
100 / 100
 13 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define all(x) x.begin(), x.end()

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}
#define int ll

int n, m, k;
int b, c, a;
int t;
vector<int> have;

void read() {
	cin >> n >> m >> k;
	cin >> a >> b >> c;
	cin >> t;
	have.resize(m);
	for (auto &i : have)
		cin >> i;
}

vector<int> cnt;
vector<int> Time;

int get_len(int i) {
	return (i + 1 < m ? have[i + 1] : n + 1) - have[i];
}

void build() {
	k -= m;
	cnt.assign(m, 0);
	Time.assign(m, 0);
	for (int i = 0; i < m; i++) {
		Time[i] = b * (have[i] - 1);
		if (Time[i] > t) {
			cnt[i] = -1;
		} else {
			cnt[i] = min((t - Time[i]) / a + 1, get_len(i));
		}
	}
}

int ans;

void add() {
	int pos_add = -1;
	int cnt_add = -1;
	for (int i = 0; i < m; i++) {
		if (cnt[i] == -1) continue;
		if (cnt[i] == get_len(i)) continue;
		if (Time[i] + c * cnt[i] > t) continue;
		int can_add = min((t - Time[i] - c * cnt[i]) / a + 1, get_len(i) - cnt[i]);
		if (can_add > cnt_add) {
			cnt_add = can_add;
			pos_add = i;
		}
	}
	if (pos_add == -1) return;
	cnt[pos_add] += cnt_add;
}

void run() {
	build();
	/*cout << "Time = " << endl;
	for (auto i : Time)
		cout << i << " ";
	cout << endl;
	cout << "cnt = " << endl;
	for (auto i : cnt)
		cout << i << " ";
	cout << endl;*/



	while(k--) {
		add();
		/*cout << "cnt = " << endl;
		for (auto i : cnt)
			cout << i << " ";
		cout << endl;*/
	}
	for (auto i : cnt) {
		if (i != -1) ans += i;
	}
}

void write() {
	cout << ans -1  << endl;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	read();
	run();
	write();
	return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 7 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 13 ms 376 KB Output is correct
24 Correct 5 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 7 ms 376 KB Output is correct
30 Correct 6 ms 376 KB Output is correct