Submission #1179662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179662		anteknne	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	3 ms	328 KiB

semiexpress

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXM = 3000;
ll s[MAXM + 1];
vector<pii> bloki;

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m, k;
    ll a, b, c;
    ll t;

    cin >> n >> m >> k >> a >> c >> b >> t;

    for (int i = 0; i < m; i ++) {
        cin >> s[i];
    }

    ll wyn = 0;
    for (int i = 0; i < m - 1; i ++) {
        ll p = (t - (s[i] - 1LL) * c)/a + s[i];
        p ++;
        ll k = s[i + 1] - 1;
        if ((s[i] - 1LL) * c > t) {
            bloki.pb({-1, -1});
            continue;
        }
        if (p > k) {
            wyn += s[i + 1] - s[i];
            bloki.pb({-1, -1});
            continue;
        }
        wyn += p - s[i];
        bloki.pb({p, k});
    }
    wyn --;
    if (t >= (n - 1LL) * c) {
        wyn ++;
    }

    /*for (auto x : bloki) {
        cout << x.st << " " << x.nd << "\n";
    }*/

    for (int i = 0; i < k - m; i ++) {
        ll rekord = -1;
        int ind = 0;
        /*for (auto x : bloki) {
            cout << x.st << " " << x.nd << "\n";
        }*/
        for (int j = 0; j < m - 1; j ++) {
            if (bloki[j].st == -1) {
                continue;
            }
            if ((t - (s[j] - 1LL) * c - (bloki[j].st - s[j]) * b) < 0) {
                continue;
            }
            ll p = (t - (s[j] - 1LL) * c - (bloki[j].st - s[j]) * b)/a + bloki[j].st;
            p = min(p, s[j + 1] - 1LL);
            if (p - bloki[j].st + 1LL >= rekord) {
                ind = j;
                rekord = p - bloki[j].st + 1LL;
            }
        }
        if (rekord == -1) {
            continue;
        }

        ll p = (t - (s[ind] - 1LL) * c - (bloki[ind].st - s[ind]) * b)/a + bloki[ind].st;
        p = min(p, s[ind + 1]);
        if (p > bloki[ind].nd) {
            bloki[ind] = {-1, -1};
        } else {
            bloki[ind] = {p + 1, bloki[ind].nd};
        }
        wyn += rekord;

    }



    cout << wyn << "\n";




    return 0;
}

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