Submission #789976

#	Time	Username	Problem	Language	Result	Execution time	Memory
789976		winter0101	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	30 ms	8692 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
long long a[3009];
map<int,int>type;
struct cus{
int u;
long long val;
bool operator < (const cus &p)const {
return val<p.val;
}
};
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n,m,k;
    cin>>n>>m>>k;
    long long x,y,z,t;
    cin>>x>>y>>z>>t;
    for1(i,1,m){
    cin>>a[i];
    type[a[i]]=1;
    }
    priority_queue<cus>t1;
    for1(i,1,m-1){
    long long cost=(a[i]-1)*y;
    if (cost>t)continue;
    int last=a[i];
    int lst=a[i];
    long long tme=(t-cost);
    tme/=x;
    last+=tme;
    //cout<<i<<" "<<last<<'\n';
    for1(j,1,k-m){
    int l=last+1,r=a[i+1]-1,nw=-1;
    while (l<=r){
        int mid=(l+r)/2;
        //cerr<<mid<<'\n';
        long long cc=1ll*(mid-a[i])*z+(a[i]-1)*y;
        cc=max(cc,1ll*(mid-1-lst)*x+(lst-a[i])*z+(a[i]-1)*y);
        if (cc<=t){
            nw=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    //cerr<<i<<" "<<nw<<" "<<last<<" "<<lst<<'\n';
    //cout<<nw<<'\n';
    //cout<<last<<'\n';
    if (nw==-1)break;
    lst=nw;
    long long vcl=(a[i]-1)*y+(lst-a[i])*z;
    tme=t-vcl;
    tme/=x;
    int len=a[i+1]-1-lst+1;
    last=nw+tme;
    t1.push({nw,min(tme+1,1ll*len)});
    }
    }
    int vcl=k-m;
    for1(i,1,vcl){
    if (t1.empty())break;
    int nw=t1.top().u;
    t1.pop();
    a[++m]=nw;
    type[nw]=2;
    //cout<<nw<<'\n';
    }
    sort(a+1,a+1+m);
    int lst=1,ans=0;
    for1(i,1,m){
    if (type[a[i]]==1){
        lst=a[i];
    }
    long long cost=(a[i]-lst)*z+(lst-1)*y;
    if (cost<=t)ans++;
    }
    ans--;
    lst=1;
    //for1(i,1,m)cout<<a[i]<<'\n';
    //cout<<m<<'\n';
    for1(i,1,m-1){
    if (type[a[i]]==1){
        lst=a[i];
    }
    int l=a[i]+1,r=a[i+1]-1;
    if (l>r)continue;
    long long cost=(a[i]-lst)*z+(lst-1)*y;
    if (cost>t)continue;
    //cout<<a[i]<<" "<<a[i+1]<<" "<<cost<<'\n';
    long long tme=t-cost;
    tme/=x;
    tme=min(tme,1ll+r-l);
    ans+=tme;
    }
    cout<<ans;
}

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