Submission #870354

#	Time	Username	Problem	Language	Result	Execution time	Memory
870354		phoenix0423	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	1 ms	604 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int N = 998244353;
const int maxn = 2e5 + 5;

struct info{
	ll get, pos, tl, id;
	info(){}
	info(ll _get, ll _pos, ll _tl, ll _id) : get(_get), pos(_pos), tl(_tl), id(_id){}
	bool operator < (const info& other) const{
		return get < other.get;
	}
};
int main(void){
	fastio;
	ll n, m, k;
	cin>>n>>m>>k;
	ll a, b, c;
	cin>>a>>b>>c;
	ll t;
	cin>>t;
	vector<ll> s(m + 1);
	for(int i = 0; i < m; i++) cin>>s[i];
	ll ans = 0;
	priority_queue<info> q;
	for(int i = 1; i < m; i++){
		ll tlf = t - b * (s[i - 1] - 1);
		if(tlf < 0) break;
		ll get = min(s[i] - s[i - 1], tlf / a + 1);
		ans += get;
		if(get < s[i] - s[i - 1]){
			ll loc = s[i - 1] + tlf / a + 1;
			ll ntlf = tlf - c * (loc - s[i - 1]);
			if(ntlf >= 0 && loc < s[i]){
				q.push({min(s[i] - loc, ntlf / a + 1), loc, ntlf, i});
			}
		}
	}
	if(b * (n - 1) > t) ans -= 1;
	k -= m;
	while(k && !q.empty()){
		auto [get, loc, tl, id] = q.top(); q.pop();
		k--;
		ans += get;
		ll nloc = loc + tl / a + 1;
		ll ntl = tl - c * (nloc - loc);
		if(ntl >= 0 && nloc < s[id]){
			q.push({min(s[id] - nloc, ntl / a + 1), nloc, ntl, id});
		}
	}
	cout<<ans<<"\n";
}

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