oj.uz

Submission #1051746

# Submission time Handle Problem Language Result Execution time Memory
1051746 2024-08-10T09:26:06 Z gagik_2007 Semiexpress (JOI17_semiexpress) C++17
18 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=5007;
ll n,m,k;
ll a,b,c;
ll t;
vector<ll>s;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("Binput.txt","r",stdin);
    // freopen("Boutput.txt","w",stdout);
    cin>>n>>m>>k;
    cin>>a>>b>>c;
    cin>>t;
    for(ll i=0;i<m;i++){
        ll x;
        cin>>x;
        s.push_back(x);
    }
    ll ans=0;
    ll cur=0;
    priority_queue<pair<ll,ll>>q;
    for(ll i=0;i<m-1;i++){
        if(cur>t)break;
        ll cnt=(t-cur)/a+1;
        if(cnt<s[i+1]-s[i]){
            ans+=cnt;
            ll pos=s[i]+cnt;
            ll rem=t-cur-cnt*c;
            if(rem>=0){
                ll cnt2=rem/a+1;
                if(cnt2+pos<s[i+1]){
                    q.push({cnt2,pos});
                }
                else{
                    q.push({s[i+1]-pos,pos});
                }
            }
        }
        else{
            ans+=s[i+1]-s[i];
        }
        cur+=(s[i+1]-s[i])*b;
    }
    if(cur<=t){
        ans++;
    }
    k-=m;
    while(!q.empty()&&k>0){
        ll cnt=q.top().ff;
        ll pos=q.top().ss;
        // cout<<cnt<<" "<<pos<<endl;
        q.pop();
        ans+=cnt;
        auto it=lower_bound(s.begin(),s.end(),pos+cnt);
        if((*it)>pos+cnt){
            ll newpos=pos+cnt;
            --it;
            ll rem=t-((*it)-1)*b-(newpos-(*it))*c;
            if(rem>=0){
                ll cnt2=rem/a+1;
                ++it;
                if(cnt2+pos<(*it)){
                    q.push({cnt2,newpos});
                }
                else{
                    q.push({(*it)-newpos,newpos});
                }
            }
        }
        k--;
    }
    cout<<ans-1<<endl;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 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 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 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 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -