oj.uz

Submission #302380

# Submission time Handle Problem Language Result Execution time Memory
302380 2020-09-18T16:09:58 Z ElyesChaabouni Hiring (IOI09_hiring) C++14
100 / 100
 828 ms 17116 KB 
#include <bits/stdc++.h>
#define MOD 998244353

using namespace std;

bool compare(pair<pair<long long, long long>, int>a, pair<pair<long long, long long>, int>b)
{
	if(a.first.first*b.first.second != a.first.second*b.first.first)
		return a.first.first*b.first.second < a.first.second*b.first.first;
	return a.first.first < b.first.first;
}
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	long long n, w;
	cin >> n >> w;
	vector<pair<pair<long long, long long>, int> >v;
	for(int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		v.push_back(make_pair(make_pair(x, y), i));
	}
	sort(v.begin(), v.end(), compare);
	priority_queue<pair<int, int> >pq;
	long long sum=0;
	long long ma=0, idx=0, ma_v_s=0, ma_v_q=0;
	for(int i = 0; i < n; i++)
	{
		sum+=v[i].first.second;
		pq.push(make_pair(v[i].first.second, v[i].second));
		while(sum*v[i].first.first > w*v[i].first.second && !pq.empty())
		{
			sum-=pq.top().first;
			pq.pop();
		}
		if(pq.size() > ma)
		{
			ma=pq.size();
			idx=i;
			ma_v_s=v[i].first.first*sum;
			ma_v_q=v[i].first.second;
		}
		else if(pq.size() == ma && ma_v_s*v[i].first.second > ma_v_q*v[i].first.first*sum)
		{
			idx=i;
			ma_v_s=v[i].first.first*sum;
			ma_v_q=v[i].first.second;
		}
	}
	while(!pq.empty())
		pq.pop();
	sum=0;
	for(int i = 0; i <= idx; i++)
	{
		sum+=v[i].first.second;
		pq.push(make_pair(v[i].first.second, v[i].second));
		while(sum*v[i].first.first > w*v[i].first.second && !pq.empty())
		{
			sum-=pq.top().first;
			pq.pop();
		}
	}
	cout << ma;
	while(!pq.empty())
	{
		cout << '\n' << pq.top().second+1;
		pq.pop();
	}
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:38:16: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   38 |   if(pq.size() > ma)
      |      ~~~~~~~~~~^~~~
hiring.cpp:45:21: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   45 |   else if(pq.size() == ma && ma_v_s*v[i].first.second > ma_v_q*v[i].first.first*sum)
      |           ~~~~~~~~~~^~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 7 ms 640 KB Output is correct
11 Correct 8 ms 640 KB Output is correct
12 Correct 11 ms 704 KB Output is correct
13 Correct 13 ms 832 KB Output is correct
14 Correct 22 ms 832 KB Output is correct
15 Correct 22 ms 832 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 29 ms 1268 KB Output is correct
5 Correct 89 ms 3664 KB Output is correct
6 Correct 478 ms 12744 KB Output is correct
7 Correct 646 ms 14032 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 4068 KB Output is correct
2 Correct 180 ms 4064 KB Output is correct
3 Correct 184 ms 4064 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 7136 KB Output is correct
2 Correct 300 ms 7000 KB Output is correct
3 Correct 299 ms 7172 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 15304 KB Output is correct
2 Correct 759 ms 15488 KB Output is correct
3 Correct 738 ms 15272 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 828 ms 17096 KB Output is correct
2 Correct 817 ms 17116 KB Output is correct
3 Correct 818 ms 17096 KB Output is correct