Submission #651693

#	Time	Username	Problem	Language	Result	Execution time	Memory
651693		four_specks	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	13 ms	4556 KiB

semiexpress

#include <bits/stdc++.h>

using namespace std;

inline namespace
{
} // namespace

void solve(int _test_ = -1)
{
    long n;
    int m, k;
    cin >> n >> m >> k;

    long a, b, c, t;
    cin >> a >> b >> c >> t;

    vector<long> s(m);
    for (long &x : s)
        cin >> x, --x;

    long cnt = 0;
    vector<long> can;
    for (int i = 0; i < m - 1; i++)
    {
        if (b * s[i] <= t)
        {
            long x = min(s[i + 1], s[i] + (t - b * s[i]) / a + 1);
            cnt += x - s[i];
            for (int j = 0; j < k - m && x < s[i + 1]; j++)
            {
                if (b * s[i] + c * (x - s[i]) <= t)
                {
                    long y = min(s[i + 1], x + (t - (b * s[i] + c * (x - s[i]))) / a + 1);
                    can.push_back(y - x);
                    x = y;
                }
                else
                    break;
            }
        }
        else
            break;
    }
    if (b * s[m - 1] > t)
        cnt--;
    sort(can.begin(), can.end(), greater<>());

    for (int i = 0; i < min(k - m, (int)can.size()); i++)
        cnt += can[i];

    cout << cnt << '\n';
}

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

    int T_ = 1;
    // cin >> T_;

    for (int t_ = 0; t_ < T_; t_++)
        solve(t_);

    return 0;
}

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