Submission #888042

#	Time	Username	Problem	Language	Result	Execution time	Memory
888042		Maite_Morale	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	1 ms	2548 KiB

semiexpress

#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 500005
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
 
ll m,n,a[MAX],b[MAX],r,t,t1,t2,t3,k;
ll cost(ll x,ll y){
    if(a[y]*t3+x*t2>t)return 0;
    return min(b[y]-x,max((ll)0,(t-(a[y]*t3+x*t2))/t1)+1);
}
int main(){
    fast_in
    cin>>n>>m>>k>>t1>>t3>>t2>>t;
    t2=min(t2,t1);t3=min(t3,t2);
    priority_queue<pair<ll,pll>> q;
    for(int i=0;i<m;i++){
        cin>>a[i];a[i]--;if(i>0)b[i-1]=a[i]-a[i-1];
    }b[m-1]=n-a[m-1]; 
    for(int i=0;i<m;i++){
        if(a[i]*t3<=t){
            ll p=cost(0,i);
            r+=p;//cout<<p<<" "<<i<<" "<<0<<"\n";
            q.push({cost(p,i),{p,i}});
        }
    }k-=m;
    while(!q.empty()){
        pair<ll,pll> u=q.top();q.pop();
        if(u.F==0 || k==0)break;
        k--;r+=u.F;//cout<<u.F<<" "<<u.S.S<<" "<<u.S.F<<"\n";
        q.push({cost(u.S.F+u.F,u.S.S),{u.S.F+u.F,u.S.S}});
    }
    cout<<r-1;
return 0;
}/*
1 2  3  4  5  6  7  8  9  10
1          1  1  1  1     1
0 10 20 30 25 15 25 25    27

*/

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