제출 #33291

#제출 시각아이디문제언어결과실행 시간메모리
33291ngkan146Semiexpress (JOI17_semiexpress)C++98
18 / 100
0 ms2200 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; int n,m,k; ll s[3005]; ll T, A, B ,C; typedef pair<ll,ll> ii; #define fi first #define se second struct cmpp{ bool operator () (ii a,ii b){ // fi = time left // b = station left ll val1 = min(a.fi / A, a.se); ll val2 = min(b.fi / A, b.se); if (val1 == val2) return a.fi < b.fi; return val1 < val2; } }; priority_queue <ii,vector<ii>,cmpp> pq; int main(){ iostream::sync_with_stdio(0); cin >> n >> m >> k; cin >> A >> B >> C; cin >> T; for(int i=1;i<=m;i++) cin >> s[i]; int ans = 0; for(int i=1;i<m;i++){ if (T < (s[i]-1) * B) break; ll time_left = T - (s[i]-1) * B; ll station_left = s[i+1] - s[i] - 1; ll passable_station = min(station_left, time_left / A); ans += passable_station; time_left -= (passable_station+1) * C; station_left -= passable_station; //cout << time_left << ' ' << station_left << endl; if (time_left >= 0 && station_left) pq.push(ii(time_left, station_left)); } for(int i=1;i<=m;i++) ans += (T >= (s[i]-1) * B); k -= m; //cout << ans-1 << endl; while(k-- && pq.size()){ ii u = pq.top(); pq.pop(); ll time_left = u.fi; ll station_left = u.se; //cout << time_left << ' ' << station_left << endl; ll passable_station = min(station_left, time_left / A + 1); ans += passable_station; time_left -= passable_station * C; if (time_left < 0 || passable_station == station_left) continue; pq.push(ii(time_left, station_left - passable_station)); //cout << ans << endl; } cout << ans - 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...