Submission #146222

#	Time	Username	Problem	Language	Result	Execution time	Memory
146222		osaaateiasavtnl	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	3 ms	504 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
const int N = 3001, INF = 1e9 + 7;
int blet, EX, SEX, A, B, C, T;
int s[N];
//A, B, C - local, express, semiexpress
int getime(int p) { int i = upper_bound(s, s + EX, p) - s - 1; return (s[i] - 1) * B + (p - s[i]) * C; }
int next(int p) { return upper_bound(s, s + EX, p) - s; }
int getr(int p) { return p + (T - getime(p)) / A; }
int get(int p) { return min(getr(p), s[next(p)] - 1) - p + 1; }
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> blet >> EX >> SEX >> A >> B >> C >> T;
    for (int i = 0; i < EX; ++i) cin >> s[i];
    priority_queue <ii> q;
    int ans = (getime(s[EX - 1]) <= T);
    for (int i = 0; i + 1 < EX; ++i) {
        if (getime(s[i]) <= T) {
            ans += get(s[i]);
            int l = getr(s[i]) + 1;
            if (l < s[i + 1] && getime(l) <= T) q.emplace(get(l), l);
        }
    }
    for (int it = 0; it < SEX - EX && q.size(); ++it) {
        int p = q.top().second; q.pop(); ans += get(p);
        int l = getr(p) + 1;
        if (l < s[next(p)] && getime(l) <= T) q.emplace(get(l), l);
    }
    cout << ans - 1 << '\n';
}   

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