WA 20 求条
查看原帖
WA 20 求条
1268478
時空楼主2025/7/25 16:21
#include <bits/stdc++.h>

#define FstIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair <ll, ll>
#define pb push_back
#define mem(a, v) memset(a, v, sizeof a)

using namespace std; 

using ll = long long; 
using ull = unsigned long long;
using ld = long double;

const ll N = 5e5 + 2, M = 2e3 + 5;
const ll inf = 1e18, mod = 1e9 + 7;
const ld eps = 1e-6;

ll n, m, k;
ll A, B, C, T;
ll S[N], R[N];

// L, R, T
// 

// R[x] 表示第 x 段当前能坐到的最远的车站
bool pp(ll x, ll y) { return x > y; }

priority_queue <pii> heap;

void sol(ll i)
{
	ll left = T - (S[i] - 1) * B - (R[i] - S[i]) * C;
	if (left <= 0) return ;
	ll val = left / A, copy = R[i];
//	cout << "sol " << i << ' ' << val << ' ' << left << '\n';
	R[i] = min(R[i] + val, S[i + 1] - 1);
	heap.push({R[i] - copy, i});
}

signed main()
{
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	
	FstIO;	
	
	cin >> n >> m >> k;
	cin >> A >> B >> C >> T;
	for (ll i = 1; i <= m; ++ i ) cin >> S[i];
	ll t = 0; t += (m - 1);
	k -= m; // vector <ll> p;
	for (ll i = 1; i < m; ++ i )
	{
		if ((S[i] - 1) * B > T) break;
		if (!(S[i + 1] - S[i] - 1)) continue; 
		if ((S[i] - 1) * B + (S[i + 1] - S[i]) * A <= T) 
			t += (S[i + 1] - S[i] - 1);
		else
		{
			ll left = T - (S[i] - 1) * B;
			ll val = left / A;
			R[i] = S[i] + val;
//			cout << i << ' ' << R[i] << ' ' << val << '\n';
			
			t += R[i] - S[i];
			sol(i);
		}
	}
//	for (ll i = 1; i < m; ++ i ) cout << R[i] << ' '; cout << '\n';
//	cout << t << '\n' << '\n';
	for (ll i = 1; i <= k; ++ i )
	{
		if (heap.empty()) break;
		auto tp = heap.top(); heap.pop();
//		cout << tp.first << ' ' << tp.second << '\n';
		t += tp.first;
		sol(tp.second);
	}
	
	cout << t << '\n';
	
	return 0;
	
	cout.flush();
}
2025/7/25 16:21
加载中...