Submission #1143048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143048		nuutsnoynton	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	1 ms	580 KiB

semiexpress

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair < ll, ll >;
using plll = pair < ll, pair < ll, ll > >;
ll a[3002];
set <ll > v;
int main() {
	ll n, m, r, left, L, x, y, i, Left, I, j, ans, t, A, B, C, s, N, k;
	
	cin >>n >> m >> k;
	n --;
	cin >> A >> B>> C;
	priority_queue < pll > q;
	priority_queue < plll > pq;
	
	cin >> N;
	
	for (i = 1; i <= m; i ++) {
		cin >> a[i];
		a[i]--;
		s = N - (a[i] * B);
		if ( s >= 0) q.push(make_pair(s, a[i]));
	}
	a[m + 1]= n + 1;
	ans = 0;
	while(!q.empty() ) {
		left = q.top().first;
		i = q.top().second;
	//	cout << left << " " <<i << endl;
		q.pop();
		s = left/A;
		s ++;
		r = upper_bound(a + 1, a + m + 2, i) - a;
		s = min(s, a[r] - i);
		ans += s;
	//	cout << s << " R" << ans << endl;
		left = left - (C * s);
		if (left < 0) continue;
		Left = left;
		I = i + s;
		s = Left/A;
		s ++;
		r = upper_bound(a+ 1 , a + m + 2, i) - a;
		s = min(s, a[r] - I);
		if ( s >= 1 && I < a[r]) {
			pq.push(make_pair(s, make_pair(Left, I)));
		}
	}
	k -= m;
	while(!pq.empty() && k --) {
		s = pq.top().first;
		left = pq.top().second.first;
		i = pq.top().second.second;
		pq.pop();
	//	cout <<i << " "<< s<< " " << left<< endl;
	//	cout << s << "S" << endl;
		ans += s;
		
		left = left - (C * s);
		if (left < 0) continue;
		Left = left;
		I = i + s;
		s = Left/A;
		s ++;
		r = upper_bound(a , a + m + 2, i) - a;
		s = min(s, a[r] - I);
		if ( s >= 1 && I < a[r]) {
			pq.push(make_pair(s, make_pair(Left, I)));
		}
	}
	cout << ans -1<< endl;
}

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