oj.uz

Submission #939331

# Submission time Handle Problem Language Result Execution time Memory
939331 2024-03-06T09:21:08 Z browntoad Semiexpress (JOI17_semiexpress) C++14
100 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define RREP1(i, n) for(int i = (n); i >= 1; i--)
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define ppi pair<pii, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)


const ll maxn = 3e5+5;
const ll maxm = 1e4+5;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;

int n, m, k;
int a, b, c;
int T;

int comp(int nx, int nv, int R){
    // if dp[nx] = nv, how much can it extend
    return min(R-nx-1, (T-nv)/a);
}
signed main(){
    IOS();
    cin>>n>>m>>k;
    cin>>a>>b>>c;
    cin>>T;

    vector<int> ex(m+1); // express

    REP(i, m){
        cin>>ex[i];
    }
    int ans = ((ex[m-1]-1)*b <= T)-1;
    priority_queue<ppp> pq;
    REP(i, m-1){ // wont calculate last one, but counted first one
        int l = ex[i], r = ex[i+1];
        int v = (ex[i]-1)*b;
        if (v > T) continue;
        ans += comp(l, v, r)+1;
        l += comp(l, v, r)+1;
        if (l < r && v+c*(l-ex[i]) <= T){
            pq.push({{comp(l, v+c*(l-ex[i]), r), v+c*(l-ex[i])}, {l, r}});
        }
    }

    k -= m;
    while(SZ(pq) && k > 0){
        ppp tp = pq.top(); pq.pop();
        int l = tp.s.f, r = tp.s.s, ext = tp.f.f, v = tp.f.s;
        ans += ext+1;

        l += ext+1;
        if (l < r && v+c*(ext+1) <= T){
            pq.push({{comp(l, v+c*(ext+1), r), v+c*(ext+1)}, {l, r}});
        }
        k--;
    }
    /*REP1(i, n){
        dp[i] = min(dp[i-1]+a, dp[i]);
        if (dp[i] <= T) ans++;
    }
    */
    cout<<ans<<endl;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct