oj.uz

Submission #161381

# Submission time Handle Problem Language Result Execution time Memory
161381 2019-11-02T06:32:04 Z oolimry Semiexpress (JOI17_semiexpress) C++14
18 / 100
 2 ms 504 KB 
#include <bits/stdc++.h>

using namespace std;

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	long long n, m, k;
	cin >> n >> m >> k;
	long long a, b, c, t;
	cin >> a >> b >> c >> t;
	
	long long ans = 0;
	
	long long pos[m];
	long long dist[m];
	for(int i = 0;i < m;i++){
		cin >> pos[i];
		dist[i] = (pos[i] - 1) * b;
	}
	
	typedef pair<long long,long long> ii;
	queue<ii> options[m];
	if(dist[m-1] <= t) ans++;
	for(int i = 0;i < m-1;i++){
		if(dist[i] > t){
			continue;
		}
		long long l = pos[i];
		long long predist = dist[i];
		/*
		ans += (t - dist[i]) / a;
		if(i != 0) ans++;
		
		l += ((t - dist[i]) / a) + 1;
		*/
		bool has = false;
		
		while(true){
			//cout << l << "\n";
			if(predist > t) break;
			if(l == pos[i+1]) break;
			long long nl = l + ((t - predist) / a) + 1;
			
			if(nl >= pos[i+1]){
				nl = pos[i+1];
			}
			if(has){
				options[i].push(ii(nl-l, i));
				if(options[i].size() > 3000) break;
				//cout << nl-l << " " << i << "\n";
			}
			else{
				has = true;
				ans += (nl-l);
			}
			predist += (nl-l)*c;
			l = nl;
			
		}
		//cout << "\n";
	}
	
	
	priority_queue<ii, vector<ii>, greater<ii> > pq;
	for(int i = 0;i < m;i++){
		if(!options[i].empty()){
			pq.push(options[i].front());
			options[i].pop();
		}
	}
	
	for(int i = 0;i < k-m;i++){
		if(pq.empty()) break;
		ii x = pq.top();
		ans += x.first;
		pq.pop();
		if(!options[x.second].empty()){
			pq.push(options[x.second].front());
			options[x.second].pop();
		}
	}
	///for the 1st station
	ans--;
	cout << ans;
	
	
	
	
}

Subtask #1
18.0 / 18.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 2 ms 416 KB Output is correct
14 Incorrect 2 ms 376 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 2 ms 416 KB Output is correct
14 Incorrect 2 ms 376 KB Output isn't correct
15 Halted 0 ms 0 KB -