Submission #446818

#	Time	Username	Problem	Language	Result	Execution time	Memory
446818		ritul_kr_singh	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	43 ms	348 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

int n, m, k, a, b, c, t, s[3000], ans, pre;
priority_queue<int> q;

void add(int v, bool y){
	ans += v;
	if(!y) return;
	q.push(-v);
	if((int)q.size() > k-m) ans += q.top(), q.pop();
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> k >> a >> b >> c >> t;
	for(int i=0; i<m; ++i) cin >> s[i];

	for(int i=0; i+1<m; ++i){
		int time = pre, diff = s[i+1] - s[i];
		for(int j=0; j<=k-m; ++j){
			int v = min(diff, (t - time + a) / a);
			if(v < 0) break;
			add(v, j);
			diff -= v;
			time += v * c;
		}

		pre += (s[i+1] - s[i]) * b;
	}

	if(pre <= t) add(1, 0);

	cout << ans - 1;
}

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