Submission #998390

#	Time	Username	Problem	Language	Result	Execution time	Memory
998390		dimashhh	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	3 ms	604 KiB

semiexpress

#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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52