Submission #1280951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280951		third	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	103 ms	103172 KiB

semiexpress

#include<bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl '\n'
#define TASK ""
#define N 9000006
#define LOG 17
using namespace std;

bool ghuy4g;

ll n, m, k;
ll A, B, C, T, s[3005], mxx[3005], lst;

int cha[N], noi[N];
bool vst[N];

vector<ll> vt;

void sub1() {
	for (int i = 1; i <= m; i ++) {
		ll used = (s[i] - 1) * B;
		if (used > T) break;
		lst = i;
		ll tiep = (T - used) / A;
		mxx[i] = s[i] + tiep;
		//cout << i << " mxx " << mxx[i] << endl;
	}
	//return;
	ll ans = 0;
	for (int i = 1; i <= lst; i ++) {
		ll rmax = mxx[i];
		ll j = i;
		while (j <= lst && rmax >= s[j]) {
			rmax = max(rmax, mxx[j]);
			j ++ ;
		}
		rmax = min(rmax, n);
		ans += (rmax - s[i] + 1);
		if (rmax == n) {
			break;
		}
		//cout << "i rmax " << s[i] << " " << rmax << endl;
		// dat o rmax + 1
		ll used = (s[j - 1] - 1) * B + (rmax + 1 - s[j - 1]) * C;
		ll prev = rmax, parent = -1, dem = 0;
		while (used <= T) {
			dem ++;
			if (dem > 3000) break;
			ll nhay = (T - used) / A + 1; // dung dc 1 cai la chinh dinh do, nhay: nhay dc bao nhieu con tu con prev
			ll den = min(prev + nhay, s[j] - 1);
			ll dung = den - prev;
			//cout << i << " " << prev << " " << used << " " << dung << endl;
			cha[vt.size()] = parent;
			if (parent != -1) {
				vst[parent] = 1;
				noi[parent] = vt.size();
			}
			vt.push_back(dung);
			parent = vt.size() - 1;
			used += ((den + 1) - (prev + 1)) * C;
			prev = den;
			if (den == s[j] - 1) {
				break;
			}
		}
		i = j - 1;
	}
	
	ll cnt = k - m;
	priority_queue<pii> pq;
	
	for (int i = 0; i < vt.size(); i ++) {
		ll it = vt[i];
		if (cha[i] == -1) {
			pq.push({it, i});
		}
	}
	
	while (pq.size() && cnt > 0) {
		auto it = pq.top();
		pq.pop();
		ans += it.fi;
		cnt -- ;
		if (vst[it.se]) {
			pq.push({vt[noi[it.se]], noi[it.se]});
		}
	}
	cout << ans - 1;
}

bool klinh;

signed main() {
   // freopen("test.inp", "r", stdin);
	//freopen("test.out", "w", stdout);
	//srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
   	cin >> n >> m >> k;
   	cin >> A >> B >> C;
   	
   	cin >> T;
   	
   	for (int i = 1; i <= m; i ++) {
   		cin >> s[i];
   	}
   	
   	
   	sub1();
   	
   	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

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