oj.uz

Submission #870941

# Submission time Handle Problem Language Result Execution time Memory
870941 2023-11-09T14:09:13 Z aaron_dcoder Semiexpress (JOI17_semiexpress) C++17
100 / 100
 1 ms 600 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 432 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 432 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 444 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 444 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 600 KB Output is correct