oj.uz

Submission #33292

# Submission time Handle Problem Language Result Execution time Memory
33292 2017-10-23T08:50:51 Z ngkan146 Semiexpress (JOI17_semiexpress) C++
100 / 100
 0 ms 2200 KB 
#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 + 1, a.se);
		ll val2 = min(b.fi / A + 1, 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;
		
		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;
}

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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