Submission #667186

#	Time	Username	Problem	Language	Result	Execution time	Memory
667186		Kahou	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	133 ms	33300 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mk make_pair
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int maxm = 3050;
ll N, A, B, C, T, S[maxm];
int M, K;
ll ans;
vector<ll> out;

void solve() {
	cin >> N >> M >> K;
	cin >> A >> B >> C;
	cin >> T;
	for (int i = 1; i <= M; i++) {
		cin >> S[i];
	}

	for (int i = 1; i < M; i++) {
		ll E = T-(S[i]-1)*B;
		ll l = S[i];
		ll t = 0;
		while (l < S[i+1] && t <= K && E >= 0) {
			ll dw = l, up = S[i+1];
			while (up - dw > 1) {
				ll md = (up+dw)/2;
				if (E-(md-l)*A < 0) up = md;
				else dw = md;
			}
			if (!t) ans += (up-l);
			else out.push_back(up-l);
			E -= (up-l)*C;
			t++;
			l = up;
		}
	}
	if (T >= (S[M]-1)*B) ans++;
	sort(out.begin(), out.end());
	for (int i = max((int)out.size()-(K-M), 0); i < (int)out.size(); i++) {
		ans += out[i];
	}
	ans--;
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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