Submission #870941

#	Time	Username	Problem	Language	Result	Execution time	Memory
870941		aaron_dcoder	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	1 ms	600 KiB

semiexpress

#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 2e18;

ll N, M, K, A, B, C, T;

struct railseg {
	ll timeleft;
	ll lengthleft;

	pair<railseg,ll> addstoptoseg() const {
		ll consumed = min(timeleft/A +1, lengthleft);
		dbg(timeleft << "," << lengthleft << ":" << consumed << "," <<timeleft-consumed*C);
		return {railseg{timeleft-consumed*C, lengthleft-consumed}, consumed};
	}

	bool operator <(const railseg& oth) const {
		return addstoptoseg().e1 < oth.addstoptoseg().e1;
	}
};

int main() {

	cin >> N >> M >> K >> A >> B >> C >> T;




	vector<ll> S(M+1);
	S[M]=N;
	for (ll i = 0; i < M; ++i)
	{
		cin >> S[i];
		S[i]--;
	}


	ll outp=0;
	priority_queue<railseg> segs;

	for (ll i = 0; i < M; ++i)
	{
		railseg curr = {T-S[i]*B, S[i+1]-S[i]};
		if (curr.timeleft<0 || curr.lengthleft<=0) 
		{
			continue;
		}
		const auto [next, eaten] = curr.addstoptoseg();
						dbgv(curr.timeleft << "," << curr.lengthleft << ":" << eaten);

		outp += eaten;

		if (next.timeleft<0 || next.lengthleft<=0) 
		{
			continue;
		}
		else 
		{
			dbgv(next.timeleft);
			dbgv(next.lengthleft);
			segs.push(next);
		}
	}

	K-=M;
	dbgv(K);


	while (!segs.empty() && K > 0) {
		railseg curr = segs.top();
		segs.pop();

		const auto [next, eaten] = curr.addstoptoseg();
		outp += eaten;
		K--;
				dbgv(curr.timeleft << "," << curr.lengthleft << ":" << eaten);


		if (next.timeleft<0 || next.lengthleft<=0) 
		{
			continue;
		}
		else {
			segs.push(next);
		}
	}

	cout << outp-1;





}

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