Submission #524002

#	Time	Username	Problem	Language	Result	Execution time	Memory
524002		Monarchuwu	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	9 ms	1996 KiB

semiexpress

// nếu đến s[i] thì đến từ s[i-1] để tối ưu
// từ s[i], đi tối đa bằng local
// đặt semi tại local + 1 và tiếp tục đi tối đa bằng local
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int M = 3000 + 3;
int n, m, k;
int a, b, c; // b < c < a
ll t, s[M];

int arr[M * M], cnt_arr;
int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m >> k; k -= m;
    cin >> a >> b >> c;
    cin >> t;
    for (int i = 1; i <= m; ++i) cin >> s[i], --s[i];

    int ans(-1);
    for (int i = 1; i < m; ++i) {
        if (s[i] * b > t) break;
        ++ans;

        ll rem = t - s[i] * b;
        int step = min(rem / a, s[i + 1] - s[i] - 1);
        ans += step;
        for (int j = s[i] + step + 1, cnt(0); (j - s[i]) * c <= rem && j < s[i + 1] && cnt < k; ++cnt) {
            step = min((rem - (j - s[i]) * c) / a, s[i + 1] - j - 1);
            arr[++cnt_arr] = step + 1;
            j += step + 1;
        }
    }
    if (s[m] * b <= t) ++ans;

    sort(arr + 1, arr + cnt_arr + 1, greater<int>());
    for (int i = 1; i <= min(cnt_arr, k); ++i) ans += arr[i];
    cout << ans << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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