Submission #1275899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275899		MisterReaper	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	4 ms	580 KiB

semiexpress

// File semiexpress.cpp created on 03.10.2025 at 14:05:21
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M, K;
    std::cin >> N >> M >> K;

    i64 A, B, C;
    std::cin >> A >> B >> C;

    i64 T;
    std::cin >> T;

    std::vector<i64> S(M + 1);
    for (int i = 0; i < M; ++i) {
        std::cin >> S[i];
        --S[i];
    }
    S[M] = N;

    std::vector<i64> f(M), tim(M);
    for (int i = 0; i < M; ++i) {
        tim[i] = S[i] * B;
        if (tim[i] > T) {
            continue;
        }
        f[i] = std::min(S[i + 1] - 1, S[i] + (T - tim[i]) / A);
    }


    for (int _ = 0; _ < K - M; ++_) {
        debug(f);
        debug(tim);

        i64 mx = -1;
        for (int i = 0; i < M; ++i) {
            if (tim[i] > T) {
                continue;
            }
            i64 ntim = tim[i] + (f[i] + 1 - S[i]) * C;
            if (ntim > T) {
                continue;
            }
            i64 nf = std::min(S[i + 1] - 1, f[i] + 1 + (T - ntim) / A);
            debug(i, ntim, nf, nf - f[i]);
            mx = std::max(mx, nf - f[i]);
        }
        if (mx == -1) {
            break;
        }
        for (int i = 0; i < M; ++i) {
            if (tim[i] > T) {
                continue;
            }
            i64 ntim = tim[i] + (f[i] + 1 - S[i]) * C;
            if (ntim > T) {
                continue;
            }
            i64 nf = std::min(S[i + 1] - 1, f[i] + 1 + (T - ntim) / A);
            if (nf - f[i] == mx) {
                f[i] = nf;
                break;
            }
        }
    }

    debug(f);
    debug(tim);

    i64 ans = 0;
    for (int i = 0; i < M; ++i) {
        if (tim[i] > T) {
            continue;
        }
        ans += f[i] - S[i] + 1;
    }

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

    return 0;
}

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