Submission #1051725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051725		SamAnd	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	127 ms	600 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 3003;

int n, m, k;
int A, B, C;
ll T;
int s[N];
int u[N];

void solv()
{
    cin >> n >> m >> k;
    cin >> A >> B >> C;
    cin >> T;
    for (int i = 1; i <= m; ++i)
        cin >> s[i];
    s[m + 1] = s[m] + 1;

    k -= m;
    int ans = 0;
    for (int i = 1; i <= m; ++i)
    {
        u[i] = s[i];
        int l = u[i], r = s[i + 1] - 1;
        int g = u[i] - 1;
        while (l <= r)
        {
            int m = (l + r) / 2;
            if ((s[i] - 1) * 1LL * B + (u[i] - s[i]) * 1LL * C + (m - u[i]) * 1LL * A <= T)
            {
                g = m;
                l = m + 1;
            }
            else
                r = m - 1;
        }
        ans += (g - u[i] + 1);
    }

    for (int ii = 0; ii < k; ++ii)
    {
        int maxu = 0;
        int maxuu = 0;
        int maxi = 0;
        for (int i = 1; i <= m; ++i)
        {
            int l = u[i], r = s[i + 1] - 1;
            int g = u[i] - 1;
            while (l <= r)
            {
                int m = (l + r) / 2;
                if ((s[i] - 1) * 1LL * B + (u[i] - s[i]) * 1LL * C + (m - u[i]) * 1LL * A <= T)
                {
                    g = m;
                    l = m + 1;
                }
                else
                    r = m - 1;
            }
            ++g;
            swap(u[i], g);
            l = u[i], r = s[i + 1] - 1;
            int gg = u[i] - 1;
            while (l <= r)
            {
                int m = (l + r) / 2;
                if ((s[i] - 1) * 1LL * B + (u[i] - s[i]) * 1LL * C + (m - u[i]) * 1LL * A <= T)
                {
                    gg = m;
                    l = m + 1;
                }
                else
                    r = m - 1;
            }
            swap(u[i], g);
            --g;
            if (gg - g > maxu)
            {
                maxu = gg - g;
                maxuu = g + 1;
                maxi = i;
            }
        }
        if (maxu == 0)
            break;
        ans += maxu;
        u[maxi] = maxuu;
    }

    --ans;
    cout << ans << "\n";
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

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