Submission #991489

#	Time	Username	Problem	Language	Result	Execution time	Memory
991489		horezushol	Semiexpress (JOI17_semiexpress)	C++14	0 / 100	283 ms	4444 KiB

semiexpress

#include<bits/stdc++.h>

const char nl = '\n';

using namespace std;
using ll = long long;


const ll N = 2e5;
ll n, m, k;
ll a, b, c;
ll t;
ll s[N];
ll p[N];

map<ll, ll> S, P;

ll dp[N]; // minimum time to get to the i-th station


void solve() {
	cin >> n >> m >> k;
	cin >> a >> b >> c;
	cin >> t;
	for (ll i = 1; i <= m; i ++) {
		cin >> s[i];
		p[i] = s[i];
		S[s[i]] = i;
		P[p[i]] = i;
	}
	for (ll i = 1; i <= n; i ++) { // only with train
		dp[i] = (i - 1)*a;
	}
	for (ll i = 1; i <= m; i ++) { // only with express
		dp[s[i]] = min(dp[s[i]], (s[i] - 1)*b);
	}
	for (ll i = 1; i <= m; i ++) { // only with semi
		dp[p[i]] = min(dp[p[i]], (p[i] - 1)*c);
	}
	for (ll i = 2; i <= n; i ++) { // train + express + semi
 		dp[i] = min(dp[i], dp[i-1] + a);
		if (S[i]) {
			dp[i] = min(dp[i], dp[s[S[i]-1]] + (i - s[S[i]-1])*b);
		}
		if (P[i]) {
			dp[i] = min(dp[i], dp[p[P[i]-1]] + (i - p[P[i]-1])*c);			
		}
 		// s[S[i]-1] position of station before that one
	}

	vector<ll> sick;
	ll res = 0;
	for (ll i = 2; i <= n; i ++) {
		if (dp[i] > t && !P[i]) {
			sick.push_back(i);
		} else {
			res ++;
		}
	}
	// ~debug
	// for (ll i = 1; i <= n; i ++) {
	// 	cout << dp[i] << " ";
	// }
	// cout << nl;
	// for (auto i : sick) {
	// 	cout << i << " ";
	// }
	// cout << nl;
	// ~
	for (ll fi = 0; fi < (ll)sick.size(); fi ++) {
		for (ll se = fi+1; se < (ll)sick.size(); se ++) {
			vector<ll> cur = {0};
			vector<ll> dp2 = {0};
			for (ll i = 1; i <= m; i ++) {
				cur.push_back(p[i]);
			}
			for (ll i = 1; i <= n; i ++) {
				dp2.push_back(dp[i]);
			}
			cur.push_back(sick[fi]);
			cur.push_back(sick[se]);
			sort(cur.begin(), cur.end());
			map<ll, ll> mp;
			for (ll i = 1; i <= m+2; i ++) {
				mp[cur[i]] = i;
			}
			for (ll i = 2; i <= n; i ++) {
		 		dp2[i] = min(dp2[i], dp2[i-1] + a);
				if (S[i]) {
					dp2[i] = min(dp2[i], dp2[s[S[i]-1]] + (i - s[S[i]-1])*b);
				}
				if (mp[i]) {
					dp2[i] = min(dp2[i], dp2[cur[mp[i]-1]] + (i - cur[mp[i]-1])*c);			
				}
			}
			ll ans = 0;
			for (ll i = 2; i <= n; i ++) {
				if (dp2[i] <= t) {
					ans ++;
				}
			}
			res = max(res, ans);
			// ~debug
			// cout << "\n------------\n";
			// for (ll i = 1; i <= m+2; i ++) {
			// 	cout << cur[i] << " ";
			// }
			// cout << nl;
			// for (ll i = 1; i <= n; i ++) {
			// 	cout << dp2[i] << " ";
			// }
			// cout << "\n------------\n";
			// ~
		}
	}
	cout << res;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll tst = 1;
	// cin >> tst;
	while (tst --) {
		solve();
		cout << nl;
	}
}

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