oj.uz

Submission #998390

# Submission time Handle Problem Language Result Execution time Memory
998390 2024-06-13T19:32:22 Z dimashhh Semiexpress (JOI17_semiexpress) C++17
100 / 100
 3 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int  N = 3e3 + 30, MOD = 1e9 + 7;
#define int ll
int n,m,k;
ll s[N],r[N];
ll t,a,b,c;
ll nx_cant(ll st,ll cost){
    if(cost < 0) return st;
    ll st1= cost / a + 1 + st;
    return st1;
}
ll cost[N];
void test(){
    cin >> n >> m >> k >> a >> b >> c >> t;
    ll res = 0;
    for(int i = 1;i <= m;i++){
        cin >> s[i];
        r[i] = s[i];
        cost[i] = (s[i] - 1) * b;
    }
    for(int i = 1;i < m;i++){
        int R = min(s[i + 1],nx_cant(s[i],t - (s[i] - 1) * b)); 
        if(cost[i]> t) continue;
        cost[i] += (R - r[i]) * c;
        r[i] = R;
    }
    // for(int i = 1;i<m;i++){
    //     cout<<i<<' '<<r[i]<<' '<<cost[i] << '\n';
    // }
    // cout << '\n';
    k -= m;
    for(int i = 1;i <= k;i++){
        ll mx = 0;
        array<ll,3> val;
        for(int j = 1;j < m;j++){
            ll left = t - cost[j];
            ll R = min(s[j + 1],nx_cant(r[j],left));
            // cout << j << ' ' << r[j] << ' ' << R << ' ' << cost[j] << '\n';
            if(R - r[j] > mx && cost[j]<= t){
                mx = R - r[j];
                val = {j,R,(R - r[j]) * c};
            }
        }
        // cout << '\n';
        if(!mx) break;
        cost[val[0]] += val[2];
        r[val[0]] = val[1];
    }
    // for(int i = 1;i <= m;i++){
    //     cout << i << ' ' << r[i] << '\n';
    // }
    res += r[1] - s[1] - 1;
    for(int i = 2;i < m;i++){
        if((s[i] -1)*b>t) continue;
        res += r[i] - s[i];
    }
    if((s[m] - 1) * b <= t){
        res++;
    }
    cout << res << '\n';
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        test();
    }
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 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 0 ms 348 KB Output is correct
16 Correct 0 ms 456 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 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 0 ms 348 KB Output is correct
16 Correct 0 ms 456 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 3 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct