Submission #691921

#	Time	Username	Problem	Language	Result	Execution time	Memory
691921		Paul_Liao_1457	Semiexpress (JOI17_semiexpress)	C++17	18 / 100	1 ms	332 KiB

semiexpress

//記得跳題
#include<iostream>
#include<array>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map>
#include<cstring>
#include<iomanip>
#include<bitset>
#include<tuple>
 
#define ll long long
#define int ll
#define LL __int128_t
#define DB double
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define INF (ll)(2e9)
#define MOD (ll)(1e9+7)
#define F first
#define S second
#define endl "\n"
#define AC ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);



using namespace std;


ll a,b,c;
 
struct func{
    bool operator()(const pair<ll,ll> &x, const pair<ll,ll> &y) const{
        return min((x.F/a),x.S)>min((y.F/a),y.S);
    }
};
 
template<class T> using PQ=priority_queue<T,vector<T>,func>;
 
void file(){
    freopen("/Users/liaoyunyang/Desktop/meta_in.txt","r",stdin);
    freopen("/Users/liaoyunyang/Desktop/meta_out.txt","w",stdout);
}

bool cmp(pair<ll,ll> &x,pair<ll,ll> &y){
    return min((x.F/a),x.S)>min((y.F/a),y.S);
}

ll ex[3005],dp[3005][3005];

signed main(){
    AC;
    ll n,m,k; cin>>n>>m>>k; k-=m;
    cin>>a>>b>>c;
    ll t; cin>>t;
    FOR(i,1,m+1) cin>>ex[i];
    
    ll tot=0,ans=0;
    PQ<pair<ll,ll> > pq;
    
    FOR(i,1,m+1){
        tot=(ex[i]-ex[1])*b;
        if(tot>t) break;
        if(i==m){
            ans++; break;
        }
        ll r=t-tot,sum=r/a;
        if(ex[i]+sum>=ex[i+1]-1){
            ans+=ex[i+1]-ex[i];
        }
        else{
            ans+=1+sum;
            ll rt=t-tot;
            if(rt>=c*(sum+1)){
                pq.push({rt-c*(sum+1),ex[i+1]-ex[i]-sum-2});
            }
        }
    }

    while(k--){
        if(!pq.size()) break;
        ll tF=pq.top().F,tS=pq.top().S; pq.pop();
        ll sum=min(tF/a,tS);
        ans+=1+sum;
        if(tF>c*(sum+1)&&sum<tS){
            pq.push({tF-c*(sum+1),tS-sum-1});
        }
    }
    cout<<ans-1<<endl;
}

 
/*
 4 5
 1 2 4 4
 1 3 2 1
 4 3 1 2
 4 1 6 1
 2 4 2 5
 
 */

Compilation message (stderr)

semiexpress.cpp: In function 'void file()':
semiexpress.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     freopen("/Users/liaoyunyang/Desktop/meta_in.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:50:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     freopen("/Users/liaoyunyang/Desktop/meta_out.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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