Submission #991278

#	Time	Username	Problem	Language	Result	Execution time	Memory
991278		horezushol	Semiexpress (JOI17_semiexpress)	C++14	0 / 100	300 ms	2556 KiB

semiexpress

#include<bits/stdc++.h>

const char nl = '\n';

using namespace std;
using ll = long long;


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

map<int, int> S, P;

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


void solve() {
	cin >> n >> m >> k;
	cin >> a >> b >> c;
	cin >> t;
	for (int i = 1; i <= m; i ++) {
		cin >> s[i];
		p[i] = s[i];
		S[s[i]] = i;
		P[p[i]] = i;
	}
	for (int i = 1; i <= n; i ++) { // only with train
		dp[i] = (i - 1)*a;
	}
	for (int i = 1; i <= m; i ++) { // only with express
		dp[s[i]] = min(dp[s[i]], (s[i] - 1)*b);
	}
	for (int i = 1; i <= m; i ++) { // only with semi
		dp[p[i]] = min(dp[p[i]], (p[i] - 1)*c);
	}
	for (int 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<int> sick;
	int res = 0;
	for (int i = 2; i <= n; i ++) {
		if (dp[i] > t) {
			sick.push_back(i);
		} else {
			res ++;
		}
	}
	for (int fi = 0; fi < (int)sick.size() - 1; fi ++) {
		for (int se = fi+1; se < (int)sick.size(); se ++) {
			vector<int> cur = {0};
			vector<int> dp2 = {0};
			for (int i = 1; i <= m; i ++) {
				cur.push_back(p[i]);
			}
			for (int 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<int, int> mp;
			for (int i = 1; i <= m+2; i ++) {
				mp[cur[i]] = i;
			}
			for (int i = 2; i <= n; i ++) {
		 		dp2[i] = min(dp[i], dp[i-1] + a);
				if (S[i]) {
					dp2[i] = min(dp[i], dp[s[S[i]-1]] + (i - s[S[i]-1])*b);
				}
				if (mp[i]) {
					dp2[i] = min(dp[i], dp[cur[mp[i]-1]] + (i - cur[mp[i]-1])*c);			
				}
			}
			int ans = 0;
			for (int i = 2; i <= n; i ++) {
				if (dp2[i] <= t) {
					ans ++;
				}
			}
			res = max(res, ans);
		}
	}
	cout << res;
	// for (int i = 1; i <= n; i ++) {
	// 	cout << dp[i] << " ";
	// }
}

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

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