oj.uz

Submission #526484

# Submission time Handle Problem Language Result Execution time Memory
526484 2022-02-15T01:30:20 Z pvviet001 Schools (IZhO13_school) C++14
100 / 100
 104 ms 17400 KB 
/* Author : Mohamed Ahmed Bakry (handle : MohamedAhmed04)

   contest name : IZhO 2013 day 1
   problem name : Schools (IZhO 13-School)
   problem link : https://oj.uz/problem/view/IZhO13_school

   Problem's solution : 
   - sort the numbers according to difference between M[i] and S[i]
   - let pref[i] = sum of highest m of value M[i] from index 0 to i
     and suff[i] = sum of highest s of value S[i] from index n-1 to i
   - answer is max(pref[i] + suff[i+1]) for all 0 <= i <= n-1

*/

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 300000 + 10 ;

long long M[MAX] , S[MAX] ;
long long prefM[MAX] , suffS[MAX] ;
int n , m , s ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m>>s ;
	vector< pair<int , int> >vp ;
	for(int i = 0 ; i < n ; ++i)
	{
		cin>>M[i]>>S[i] ;
		vp.push_back({M[i]-S[i] , i}) ;
	}
	sort(vp.rbegin() , vp.rend()) ;
	priority_queue< long long , vector<long long> , greater<long long> >q ;
	long long sum = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		int idx = vp[i].second ;
		if(q.size() < m)
		{
			sum += M[idx] ;
			q.push(M[idx]) ;
		}
		else if(q.top() < M[idx])
		{
			sum -= q.top() ;
			q.pop() ;
			sum += M[idx] ;
			q.push(M[idx]) ;
		}
		prefM[i] = sum ;
	}
	while(q.size() > 0)
		q.pop() ;
	sum = 0 ;
	for(int i = n-1 ; i >= 0 ; --i)
	{
		int idx = vp[i].second ;
		if(q.size() < s)
		{
			sum += S[idx] ;
			q.push(S[idx]) ;
		}
		else if(q.top() < S[idx])
		{
			sum -= q.top() ;
			q.pop() ;
			sum += S[idx] ;
			q.push(S[idx]) ;
		}
		suffS[i] = sum ;
	}
	long long ans = suffS[0] ;
	for(int i = 0 ; i < n ; ++i)
		ans = max(ans , prefM[i] + suffS[i+1]) ;
	return cout<<ans<<"\n" , 0 ;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:42:15: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |   if(q.size() < m)
      |      ~~~~~~~~~^~~
school.cpp:62:15: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |   if(q.size() < s)
      |      ~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 13 ms 2736 KB Output is correct
14 Correct 24 ms 4596 KB Output is correct
15 Correct 41 ms 8376 KB Output is correct
16 Correct 57 ms 11976 KB Output is correct
17 Correct 79 ms 13240 KB Output is correct
18 Correct 91 ms 14332 KB Output is correct
19 Correct 92 ms 15312 KB Output is correct
20 Correct 104 ms 17400 KB Output is correct