Submission #1013884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013884		snpmrnhlol	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	97 ms	604 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e3;
ll v[N];
ll v2[N];
ll n,m,k,a,b,c,t;
ll get(ll pos){
    ll l = 0,r = m - 1;
    while(l != r){
        ll mij = (l + r + 1)/2;
        if(pos < v[mij]){
            r = mij - 1;
        }else{
            l = mij;
        }
    }
    return v[l];
}
int main(){
    cin>>n>>m>>k;
    cin>>a>>b>>c;
    cin>>t;
    k-=m;
    for(ll i = 0;i < m;i++){
        cin>>v[i];
        v2[i] = v[i];
        v[i]--;
        v2[i]--;
    }
    ll k2 = m;
    for(ll i = 0;i < k;i++){
        ll poscand = 0,nrcand = -1;
        for(ll i = 0;i < k2 - 1;i++){
            ///find first bad
            ll pos = get(v2[i]);
            ll nxt = v2[i] + (t - pos*b - (v2[i] - pos)*c)/a;
            if(v2[i + 1] <= nxt - 1 || t - pos*b - (v2[i] - pos)*c < 0 || t - pos*b - (nxt + 1 - pos)*c < 0)continue;
            ll nxt2 = min(nxt + 1 + (t - pos*b - (nxt + 1 - pos)*c)/a,v2[i + 1] - 1);
            ///[nxt + 1,nxt2]
            if(nrcand < nxt2 - nxt){
                nrcand = nxt2 - nxt;
                poscand = nxt + 1;
            }
        }
        if(nrcand == -1)break;
        v2[k2++] = poscand;
        sort(v2,v2 + k2);
    }
    ll ans = 0;
    for(ll i = 0;i < k2 - 1;i++){
        ///find first bad
        ll pos = get(v2[i]);
        ll nxt = v2[i] + (t - pos*b - (v2[i] - pos)*c)/a;
        if(t - pos*b - (v2[i] - pos)*c < 0)continue;
        ans+=min(v2[i + 1] - 1,nxt) - v2[i] + 1;
        //cout<<"segment:"<<v2[i]<<' '<<v2[i + 1] - 1<<' '<<nxt<<'\n';
    }
    if(b*v2[k2 - 1] <= t){
        ans++;
    }
    /*for(ll i = 0;i < k2;i++){
        cout<<v2[i]<<' ';
    }
    cout<<'\n';*/
    cout<<ans - 1<<'\n';
    return 0;
}

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