oj.uz

Submission #365033

# Submission time Handle Problem Language Result Execution time Memory
365033 2021-02-10T19:24:58 Z GioChkhaidze Semiexpress (JOI17_semiexpress) C++14
100 / 100
 11 ms 5484 KB 
#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define F first
#define S second

using namespace std;

const int N = 3333;

vector < ll > v[N];
ll n, m, k, A, B, C, T, c[N];
set < pair < ll , pair < ll , ll > > > st; 
set < pair < ll , pair < ll , ll > > > :: iterator it;
 
main () {
	cin >> n >> m >> k;
	cin >> A >> B >> C;
	cin >> T;
	for (int i = 1; i <= m; ++i) {
		cin >> c[i];
	}
	
	ll ans = -1, kk = k - m, cur, rcur, ls, cost;
	for (int i = 1; i < m; ++i) {
		cur = (c[i] - c[1]) * B; 
		if (cur > T) break;
		cost = min(c[i + 1] - c[i] - 1, (T - cur) / A) + 1;
		ls = c[i] + cost;	
		ans += cost;		
				
		for (int j = 1; j <= kk; ++j) {
			rcur = cur + (ls - c[i]) * C;
			if (rcur > T) break;
			if (ls >= c[i + 1]) break;		

			cost = min(c[i + 1] - ls - 1, (T - rcur) / A) + 1;
			v[i].pb(cost);
			ls += cost;		 
		}
	}

	if ((c[m] - c[1]) * B <= T) 
		++ans;

	for (int i = 1; i < m; ++i) 
		if (v[i].size()) st.insert({v[i][0], {i, 0}});
	
	for (int i = 1; i <= kk; ++i) {
		if (!st.size()) break;
		it = st.end(); --it;
		int I = (*it).S.F;
		int J = (*it).S.S;
		ans += v[I][J];
		 
		st.erase(st.find({v[I][J], {I, J}}));
		
		if (v[I].size()!= ++J) 
			st.insert({v[I][J], {I, J}});
	}
	
	cout << ans << "\n";
}

Compilation message

semiexpress.cpp:17:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   17 | main () {
      |       ^
semiexpress.cpp: In function 'int main()':
semiexpress.cpp:59:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |   if (v[I].size()!= ++J)
      |       ~~~~~~~~~~~^~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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