Submission #365033

#	Time	Username	Problem	Language	Result	Execution time	Memory
365033		GioChkhaidze	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	11 ms	5484 KiB

semiexpress

#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 (stderr)

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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52