제출 #1256864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256864		altern23	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	1 ms	328 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define sec second
#define pii pair<ll, ll>

const int MAXN = 3e3;
const ll INF = 1e18;

ll H[MAXN + 5];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll N, M, K; cin >> N >> M >> K;
	ll J, B, A; cin >> J >> B >> A;
	ll D; cin >> D;
	for(int i = 1; i <= M; i++) cin >> H[i];
	H[M + 1] = N + 1;
	ll sisa = K - M;
	priority_queue<pair<ll, pii>> pq;
	
	ll ans = 0;
	for(int i = 1; i <= M; i++){
		ll time = B * (H[i] - 1);
		if(time > D) break;
		ll lf = H[i] + 1, rg = H[i + 1] - 1, pt = H[i];
		for(;lf <= rg;){
			ll mid = (lf + rg) / 2;
			if(time + J * (mid - H[i]) <= D){
				pt = mid;
				lf = mid + 1;
			}
			else rg = mid - 1;
		}
		ans += pt - H[i] + 1;
		if(pt + 1 != H[i + 1]){
			pt++;
			lf = pt, rg = H[i + 1] - 1;
			ll pt2 = -1;
			for(;lf <= rg;){
				ll mid = (lf + rg) / 2;
				if(time + A * (pt - H[i]) + J * (mid - pt) <= D){
					pt2 = mid;
					lf = mid + 1;
				}
				else rg = mid - 1;
			}
			if(pt2 != -1) pq.push({pt2 - pt + 1, {i, pt2 + 1}});
		}
	}
	
	for(;!pq.empty() && sisa;){
		sisa--;
		auto [dist, node] = pq.top(); pq.pop();
		ans += dist;
		if(node.sec != H[node.fi + 1]){
			ll lf = node.sec, rg = H[node.fi + 1] - 1, pt = -1;
			for(;lf <= rg;){
				ll mid = (lf + rg) / 2;
				if(B * (H[node.fi] - 1) + A * (node.sec - H[node.fi]) + J * (mid - node.sec) <= D){
					pt = mid;
					lf = mid + 1;
				}
				else rg = mid - 1;
			}
			if(pt != -1){
				pq.push({pt - node.sec + 1, {node.fi, pt + 1}});
			}
		}
	}
	
	cout << ans - 1 << "\n";
}

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