Submission #1356774

#TimeUsernameProblemLanguageResultExecution timeMemory
1356774gaySemiexpress (JOI17_semiexpress)C++20
100 / 100
86 ms11588 KiB
#include <bits/stdc++.h>
#include <experimental/random>
#include <random>

//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;

using namespace std;

using ld = long double;
using ll = long long;

const ll INF = 3e18, MOD = 1e9 + 7;

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) {
        solve();
    }
}

void solve() {
    ll n, m, k; cin >> n >> m >> k;
    ll a, b, c; cin >> a >> b >> c;
    ll t; cin >> t;
    vector<ll> num(m);
    for (int i = 0; i < m; i++) {
        cin >> num[i]; num[i]--;
    }
    k = k - m;
    vector<vector<ll>> dp(m, vector<ll>(k + 1, -INF));
    dp[0][0] = 0;
    for (int i = 1; i < m; i++) {
        ll time = t - num[i - 1] * b;
        if (time < 0) {
            for (int j = 0; j <= k; j++) {
                dp[i][j] = dp[i - 1][j];
            }
            continue;
        }
        ll cnt = 0, prev = num[i - 1];
        bool flag = (t - num[i] * b >= 0);
        for (int col = 0; col <= k; col++) {
            if (time < 0 || prev >= num[i]) break;
            ll z = min(num[i] - 1 - prev, time / a);
            cnt += z;
            for (int j = 0; j + col <= k; j++) {
                dp[i][j + col] = max(dp[i][j + col], dp[i - 1][j] + cnt + flag);
            }
            time -= (z + 1) * c;
            prev += z + 1; cnt++;
        }
    }
    ll ans = 0;
    for (int i = 0; i <= k; i++) {
        ans = max(ans, dp[m - 1][i]);
    }
    cout << ans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...