#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 3e3 + 16;
const ll Log2 = 19;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
///Road to EF/M
set<ll> place;
struct point{
ll pot,pos,t;
};
bool operator < (point a,point b){
return a.pot < b.pot;
}
priority_queue<point> pq;
ll n,m,k,T,A,C,B,S[N],ans;
ll cur;
ll Cal_pot(ll pos,ll tg){
ll nxt = *place.upper_bound(pos); //cout<<nxt; exit(0);
ll inc = min(nxt - pos - 1,(T - tg)/A);
return inc + 1;
}
void out(priority_queue<point> p){
while(!p.empty()){
point now = p.top(); p.pop();
cout<<now.pot<<" "<<now.pos<<" "<<now.t<<"\n";
}
exit(0);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "tst"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
}
cin>>n>>m>>k>>A>>B>>C>>T; k -= m;
for (ll i = 1;i <= m;i++) cin>>S[i],place.insert(S[i]);
for (ll i = 1;i <= m;i++){
if (cur > T) break;
if (i == m){
ans++; break;
}
ll inc = min(S[i + 1] - S[i] - 1,(T - cur)/A);
//cout<<cur<<"\n"; //exit(0);
ans += inc + 1; inc++;
if (S[i] + inc< S[i + 1] && cur + C*inc <= T)
pq.push({Cal_pot(S[i] + inc,cur + C*inc),S[i] + inc,cur + C*inc});
cur += B*(S[i + 1] - S[i]);
}
ans--; //out(pq);
//cout<<ans; return 0;
while(k-- && !pq.empty()){
point now = pq.top(); pq.pop();
ans += now.pot; place.insert(now.pos);
ll nxt = *place.upper_bound(now.pos),cand = now.pos + now.pot,inc = now.pot;
if (cand < nxt && now.t + C*inc <= T)
pq.push({Cal_pot(cand,now.t + C*inc),cand,now.t + C*inc});
}
cout<<ans;
}
Compilation message
semiexpress.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization "O2"
|
semiexpress.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
semiexpress.cpp: In function 'int main()':
semiexpress.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
324 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
324 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
320 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
216 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
324 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
320 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
216 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
2 ms |
460 KB |
Output is correct |
24 |
Correct |
1 ms |
460 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
460 KB |
Output is correct |
28 |
Correct |
1 ms |
460 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
2 ms |
320 KB |
Output is correct |