oj.uz

Submission #312686

# Submission time Handle Problem Language Result Execution time Memory
312686 2020-10-14T05:15:16 Z joseacaz Hiring (IOI09_hiring) C++17
53 / 100
 1500 ms 21576 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#define MAXN 500005

using namespace std;
typedef long long lld;

struct Workers
{
	lld ind;
	double s, q;
};

lld N, W, amount_w, max_w;
double price_q, tot_s, max_s, prices[MAXN];
Workers worker[MAXN];
vector < lld > list, workerList;

bool cmp ( Workers _a, Workers _b )
{
	if ( _a.q == _b.q )
		return _a.s < _b.s;
	return _a.q < _b.q;
}

int main ()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> W;
	for ( lld i = 0; i < N; i++ )
		cin >> worker[i].s >> worker[i].q, worker[i].ind = i + 1;
	
	sort ( worker, worker + N, cmp );

	for ( lld i = 0; i < N; i++ )
		prices[i] = worker[i].s / worker[i].q;
	
	sort ( prices, prices + N );
	
	for ( lld i = 0; i < N; i++ )
	{
		if ( i > 0 && prices[i] == prices[i - 1] )
			continue;
		price_q = prices[i];
		amount_w = 0;
		tot_s = 0;
		workerList.clear();
		for ( lld j = 0; j < N; j++ )
			if ( price_q * worker[j].q >= worker[j].s && tot_s + (price_q * worker[j].q) <= W )
				amount_w++, tot_s += price_q * worker[j].q, workerList.push_back(worker[j].ind);

		if ( amount_w > max_w )
		{
			max_w = amount_w;
			max_s = tot_s;
			list = workerList;
		}
		else if ( amount_w == max_w && tot_s < max_s )
		{
			tot_s = max_s;
			list = workerList;
		}
	}
	
	cout << max_w << "\n";
	for ( lld i = 0; i < list.size(); i++ )
		cout << list[i] << "\n";
	return 0;
}

Compilation message

hiring.cpp: In function 'int main()':
hiring.cpp:67:21: warning: comparison of integer expressions of different signedness: 'lld' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for ( lld i = 0; i < list.size(); i++ )
      |                   ~~^~~~~~~~~~~~~

Subtask #1
26.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 8 ms 384 KB Output is correct
7 Partially correct 8 ms 512 KB Partially correct
8 Partially correct 22 ms 512 KB Partially correct
9 Correct 49 ms 632 KB Output is correct
10 Correct 30 ms 640 KB Output is correct
11 Correct 126 ms 640 KB Output is correct
12 Correct 22 ms 888 KB Output is correct
13 Partially correct 222 ms 768 KB Partially correct
14 Correct 602 ms 1144 KB Output is correct
15 Partially correct 395 ms 1272 KB Partially correct

Subtask #2
18.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Partially correct 1 ms 384 KB Partially correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1356 ms 1580 KB Output is correct
5 Correct 375 ms 3392 KB Output is correct
6 Execution timed out 1600 ms 13048 KB Time limit exceeded
7 Execution timed out 1600 ms 16888 KB Time limit exceeded

Subtask #3
3.0 / 6.0

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

Subtask #4
3.0 / 6.0

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

Subtask #5
3.0 / 6.0

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

Subtask #6
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1588 ms 5556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1592 ms 8824 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1590 ms 19448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1582 ms 21576 KB Time limit exceeded
2 Halted 0 ms 0 KB -