Submission #1256868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256868		djsksbrbf	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	7 ms	4540 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair <int, int> pii;
#define fi first
#define se second
#define pb push_back
const int MOD = 1e9 + 7;
const int MAX = 2e5 + 5;

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, m, k; cin >> n >> m >> k;
	int j, b, a; cin >> j >> b >> a;
	int d; cin >> d;
	k-= m;
	int h[m + 1];
	for(int i = 1 ; i <= m ; i++)cin >> h[i];
	
	ll ans = 0;
	priority_queue <int> unvis;
	for(int i = 1 ; i < m ; i++){
		ll tim = (h[i] - 1)*b;
		
		if(tim > d)break;
		ans++;
		
		ll stations = h[i + 1] - h[i] - 1;
		ll sisa = (d - tim) / j;
		sisa = min(sisa, stations);
		ans += sisa;
		ll prev = h[i] + sisa;
		
		for(int t = 0 ; t < k ; t++){
			int cur = prev + 1;
			if(cur >= h[i + 1])break;
			
			ll newt = (cur - h[i])*a + tim;
			if(newt > d)break;
			
			stations = h[i + 1] - cur - 1;
			sisa = (d - newt) / j;
			sisa = min(sisa, stations);
			
			unvis.push(sisa + 1);
			prev = cur + sisa;
		}
	}
	
	if((h[m] - h[1])*b <= d)ans++;
	while(k && unvis.size()){
		k--;
		ans+= unvis.top();
		unvis.pop();
	}
	cout << ans - 1 << endl;
	
	return 0;
}

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