oj.uz

Submission #691929

# Submission time Handle Problem Language Result Execution time Memory
691929 2023-02-01T01:44:48 Z Paul_Liao_1457 Semiexpress (JOI17_semiexpress) C++17
100 / 100
 1 ms 352 KB 
//記得跳題
#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);
        //cout<<"sum="<<sum<<endl;
        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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 292 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 292 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 292 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 328 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 352 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 212 KB Output is correct