Submission #755527

#	Time	Username	Problem	Language	Result	Execution time	Memory
755527		PixelCat	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	10 ms	5440 KiB

semiexpress

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^=
    int n, m, k; cin >> n >> m >> k; k -= m;
    int A, B, C; cin >> A >> B >> C;
    int T; cin >> T;
    vector<int> ve(m);  // express
    for(auto &i:ve) {
        cin >> i; i--;
    }
    ve.eb(n);

    vector<vector<int>> val(m);
    For(i, 0, m - 1) {
        int ptr = ve[i];
        For(k2, 0, k) {
            int rem = T - B * ve[i] - C * (ptr - ve[i]);
            if(rem < 0) break;
            int ptr2 = min(ve[i + 1] - 1, ptr + rem / A);
            if(ptr2 < ptr) break;
            val[i].eb(ptr2 - ptr + 1);
            ptr = ptr2 + 1;
        }
    }

    vector<int> cur(m, 1);
    int ans = 0;
    For(i, 0, m - 1) {
        if(sz(val[i])) ans += val[i][0];
    }
    while(k--) {
        int mx = -1, mxi = -1;
        For(i, 0, m - 1) {
            if(cur[i] < sz(val[i]) && val[i][cur[i]] > mx) {
                mx = val[i][cur[i]];
                mxi = i;
            }
        }
        if(mx < 0) break;
        ans += mx;
        cur[mxi]++;
    }
    cout << ans - 1 << "\n";
    return 0;
}

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