oj.uz

Submission #245651

# Submission time Handle Problem Language Result Execution time Memory
245651 2020-07-07T03:43:34 Z Joky Semiexpress (JOI17_semiexpress) C++14
100 / 100
 6 ms 512 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define li 300005
#define mp make_pair
#define pb push_back
#define pi pair<lo int, int>
#define endl "\n"
#define IOS  ios::sync_with_stdio(0); cin.tie(0);
#define fi first
#define se second
#define pii pair<ll,ll>
#define pq priority_queue
#define UwU              uwu
#define UwU              Mikuwu
#define Miku             best_waifu
#define Miku_dancing     god_waving
#define Miku_singing     god_shaking
#define a_Miku           cho_doi_bot_ngu

int n, m, k, s[30005], mx;
long long  a, b, c, t, rem[30005], ans;
pq< pair<int, int> > q;

long long int calc(int ind){
	long long tut = (t - (s[ind] - 1) * b - (s[ind + 1] - s[ind] - 1 - rem[ind]) * c);
	if(tut < c) return 0;
	return min(rem[ind], (tut - c) / a + 1);
}
int main(){
	cin >> n >> m >> k >> a >> b >> c >> t;
	for(int i = 1; i <= m ; i ++){
	    cin >> s[i];
	}
	for(int i = 1; i < m ; i ++){
		if((s[i] - s[1]) * b > t) break; 
		mx = i;
	}
	for(int i = 1; i <= mx ; i ++){
		rem[i] = max(0ll, (s[i + 1] - s[i] - 1) - (t - (s[i] - 1) * b) / a);
		q.push(mp(calc(i), i));
	}
	k -= m;
	while(k --){
		int temp = q.top().fi;
		int ind = q.top().se;
		q.pop();
		rem[ind] -= temp;
		q.push(mp(calc(ind), ind));
	}
	for(int i = 1; i <= mx; i ++){
		ans += s[i + 1] - s[i] - rem[i];
	}
	if((s[m] - 1) * b <= t) ans ++;
	cout << ans - 1; 
	return 0;
}

Compilation message

semiexpress.cpp:21:0: warning: "UwU" redefined
 #define UwU              Mikuwu
 
semiexpress.cpp:20:0: note: this is the location of the previous definition
 #define UwU              uwu

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 416 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 416 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 6 ms 256 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct

Subtask #3
52.0 / 52.0

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