oj.uz

Submission #870354

# Submission time Handle Problem Language Result Execution time Memory
870354 2023-11-07T13:23:47 Z phoenix0423 Semiexpress (JOI17_semiexpress) C++17
100 / 100
 1 ms 604 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int N = 998244353;
const int maxn = 2e5 + 5;

struct info{
	ll get, pos, tl, id;
	info(){}
	info(ll _get, ll _pos, ll _tl, ll _id) : get(_get), pos(_pos), tl(_tl), id(_id){}
	bool operator < (const info& other) const{
		return get < other.get;
	}
};
int main(void){
	fastio;
	ll n, m, k;
	cin>>n>>m>>k;
	ll a, b, c;
	cin>>a>>b>>c;
	ll t;
	cin>>t;
	vector<ll> s(m + 1);
	for(int i = 0; i < m; i++) cin>>s[i];
	ll ans = 0;
	priority_queue<info> q;
	for(int i = 1; i < m; i++){
		ll tlf = t - b * (s[i - 1] - 1);
		if(tlf < 0) break;
		ll get = min(s[i] - s[i - 1], tlf / a + 1);
		ans += get;
		if(get < s[i] - s[i - 1]){
			ll loc = s[i - 1] + tlf / a + 1;
			ll ntlf = tlf - c * (loc - s[i - 1]);
			if(ntlf >= 0 && loc < s[i]){
				q.push({min(s[i] - loc, ntlf / a + 1), loc, ntlf, i});
			}
		}
	}
	if(b * (n - 1) > t) ans -= 1;
	k -= m;
	while(k && !q.empty()){
		auto [get, loc, tl, id] = q.top(); q.pop();
		k--;
		ans += get;
		ll nloc = loc + tl / a + 1;
		ll ntl = tl - c * (nloc - loc);
		if(ntl >= 0 && nloc < s[id]){
			q.push({min(s[id] - nloc, ntl / a + 1), nloc, ntl, id});
		}
	}
	cout<<ans<<"\n";
}

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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