Submission #776093

#	Time	Username	Problem	Language	Result	Execution time	Memory
776093		TheOpChicken	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	1 ms	468 KiB

semiexpress

#include <iostream>
#include <set>
using namespace std;

const int maxN = 3e3 + 5;
long long sarr[maxN], unreachable[maxN];

set<pair<long long, long long> > s;

long long A, B, C, T;

int main(){
	int n, m, k;
	cin >> n >> m >> k;

	cin >> A >> B >> C >> T;

	sarr[0] = 0;
	for (int i = 1; i <= m; i++) cin >> sarr[i],  sarr[i]--;
	sarr[m+1] = n;

	int ans = 0;

	for (int i = 0; i <= m; i++){
		if (sarr[i] == sarr[i+1]) continue;
		long long cons = sarr[i] * B;
		unreachable[i] = (T-cons+A)/A;
		unreachable[i] = min(unreachable[i], sarr[i+1] - sarr[i]);
		unreachable[i] = max(unreachable[i], 0ll);

		ans += unreachable[i];
	}

	for (int i = 0; i <= m; i++){
		if (sarr[i] == sarr[i+1]) continue;
		long long cons = sarr[i]*B + unreachable[i]*C;
		long long next = (T-cons+A)/A + unreachable[i];
		next = min(next, sarr[i+1] - sarr[i]);
		next = max(next, unreachable[i]);


		s.insert(make_pair(next-unreachable[i], i));
		unreachable[i] = next;
	}


	int count = 0;
	while(count < k-m){
		pair<long long, long long> best = *s.rbegin(); s.erase(--s.end());
		ans += best.first;
			
		int i = best.second;
		long long cons = sarr[i]*B + unreachable[i]*C;
		long long next = (T-cons+A)/A + unreachable[i];

		next = min(next, sarr[i+1] - sarr[i]);
		next = max(next, unreachable[i]);

		s.insert(make_pair(next-unreachable[i], i));
		unreachable[i] = next;

		count++;
	}

	cout << ans-1 << endl;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52