Submission #1254540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254540		Zanite	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	455 ms	30640 KiB

semiexpress

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

using ll = long long;

const int MX = 3'023;

ll n;
int n_stations, n_extra;
ll t_walk, t_express, t_semi, t_bound;
ll stations[MX];

ll gain[MX][MX];
// gain[i][j]: at the i-th gap, if we spend j extra stations,
// how many visits can we gain

ll dp[MX][MX];

int main() {
    cin >> n >> n_stations >> n_extra;
    n_extra -= n_stations;

    cin >> t_walk >> t_express >> t_semi;
    cin >> t_bound;

    for (int i = 1; i <= n_stations; i++) cin >> stations[i];

    ll guaranteed = 0;
    for (int i = 1; i <= n_stations; i++) {
        ll reach_time = (stations[i] - 1) * t_express;
        if (reach_time > t_bound) break;
        guaranteed++;
        if (i == n_stations) break;

        ll t_rem = t_bound - reach_time;

        ll walk_dist = t_rem / t_walk;
        gain[i][0] = walk_dist;

        for (int j = 1; j <= n_extra; j++) {
            ll cur_t_semi = (walk_dist + 1) * t_semi;
            if (cur_t_semi > t_rem) break;

            gain[i][j] = gain[i][j-1] + 1;
            t_rem -= cur_t_semi;
            walk_dist = t_rem / t_walk;
            gain[i][j] += walk_dist;
        }

        for (int j = 0; j <= n_extra; j++) gain[i][j] = min(gain[i][j], stations[i+1] - stations[i] - 1);
        for (int j = 1; j <= n_extra; j++) gain[i][j] = max(gain[i][j], gain[i][j-1]);
    }

    dp[0][0] = guaranteed - 1;
    for (int i = 1; i < n_stations; i++) {
        for (int j = 0; j <= n_extra; j++) {
            for (int k = 0; k <= j; k++) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-k] + gain[i][k]);
            }
        }
    }
    cout << dp[n_stations-1][n_extra] << "\n";
}

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