Submission #1352979

#TimeUsernameProblemLanguageResultExecution timeMemory
1352979iamhereforfunSemiexpress (JOI17_semiexpress)C++20
100 / 100
185 ms33396 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))
#define int long long

const int N = 5e5 + 5;
const int M = 1 << 5;
const int K = 19;
const int LG = 20;
const long long INF = 3e18;
const int C = 26;
const int B = 1000;
const int MOD = 1e9 + 7;

int n, m, k, s[N], b, c, a;
long long t, ans;
priority_queue<long long> pq;

inline void solve()
{
    cin >> n >> m >> k >> a >> b >> c >> t;
    ans = 0;
    for (int x = 0; x < m; x++)
    {
        cin >> s[x];
    }
    for (int x = 0; x < m - 1; x++)
    {
        long long tme = (s[x] - 1) * b;
        int last = s[x];
        for (int y = 0; y < k; y++)
        {
            if (tme > t)
                break;
            long long dis = (t - tme) / a;
            if (y == 0)
            {
                if (dis + last >= s[x + 1])
                {
                    dis = s[x + 1] - 1 - last;
                }
                ans += dis + 1;
                // cout << dis << " " << tme << " " << last << "v\n";
                if (dis < (t - tme) / c && dis - 1 < s[x + 1])
                    dis++;
                else
                    break;
                tme += dis * c;
                last += dis;
            }
            else
            {
                if (dis + last >= s[x + 1])
                {
                    dis = s[x + 1] - 1 - last;
                }
                pq.push(-dis - 1);
                if (dis < (t - tme) / c && dis - 1 < s[x + 1])
                    dis++;
                else
                    break;
                tme += dis * c;
                last += dis;
            }
        }
    }
    if ((n - 1) * b <= t)
        ans++;
    while (pq.size() > k - m)
    {
        pq.pop();
    }
    while (!pq.empty())
    {
        ans -= pq.top();
        pq.pop();
    }
    cout << ans - 1 << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...