Submission #670452

#	Time	Username	Problem	Language	Result	Execution time	Memory
670452		NothingXD	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	7 ms	340 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
    ull q = (ull)((L(m) * a) >> 64);
    ull r = a - q * b; // can be proven that 0 <= r < 2*b
    return r >= b ? r - b : r;
  }
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e3 + 10;

ll n, A[maxn], idx[maxn], m, k, a, b, c;
ll t;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m >> k >> a >> b >> c >> t;

	int ans = 0;

	for (int i = 1; i <= m; i++){
		cin >> A[i];
		A[i]--;
		if (A[i] * b <= t) ans++;
	}


	for (int i = 1; i < m; i++){
		if (A[i] * b > t) break;
		ll tmp = t - A[i] * b;
		tmp = min(tmp / a, A[i+1] - A[i] - 1);
		ans += tmp;
		idx[i] = A[i] + tmp + 1;
	}

	for (int i = 1; i <= k-m; i++){
		ll res = 0;
		ll ptr = 0;
		for (int j = 1; j < m; j++){
			if (A[j] * b > t) break;
			if (idx[j] == A[j+1]) continue;
			if (A[j] * b + (idx[j] - A[j]) * c > t) continue;
			ll cnt = 1;
			ll tmp = t - A[j] * b - (idx[j] - A[j]) * c;
			cnt += min(tmp / a, A[j+1] - idx[j] - 1);
			if (res < cnt){
				res = cnt;
				ptr = j;
			}
		}
		ans += res;
		if (ptr != 0){
			idx[ptr] += res;
		}
	}

	cout << ans - 1 << '\n';

	return 0;
}

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