My (perhaps over complicated) approach to solve the fourth problem was as follows. To order N meals : * let s be the sum of all the values of b[i] (1 <= i <= N) * one meal k must be served as the first meal , that would decrease s by b[k] then increase s by a[k] , hence it's optimal to choose k that minimizes a[k] - b[k] * s <--- s + a[k] - b[k]

Then , to choose the best N — 1 meals , we either have to : Remove meal m != k which maximizes b[m] ( s <--- s - b[m] ) , or Remove meal k , and replace it with meal j which minimizes a[j] - b[j] ( s <--- s + a[j] - b[j]) We repeat the process N — 1 times to find the required answers for k = 1 through N

I only managed to implement it using 2 STL sets , which seems to exceed the memory limit of 32 MB (My solution passes 3 / 5 of official testcases scoring 72 / 120 , and returns SIGABRT on the remaining two)

I'd appreciate it a lot if someone expalins the intended approaches of this problem , or suggest some improvements (if any) to implement the above method

#include <cstdio>
#include <set>
using namespace std;

const int MAXN = 500001;
int N;
int a[MAXN];
int b[MAXN];
long long res[MAXN];
long long bsum;
int a_idx;
set < pair < int , int > > ordered_by_b;
set < pair < int , int > > ordered_by_diff;
set < pair < int , int > >::iterator it1;
set < pair < int , int > >::iterator it2;
pair < int , int > p1;
pair < int , int > p2;

int main(){
	scanf("%d" , &N);
	if(N > 100000)
		goto FAIL;
	for(int n = 1 ; n <= N ; n++){
		scanf("%d %d" , &a[n] , &b[n]);
		bsum += b[n];
		ordered_by_b.insert(make_pair(-b[n] , n));
		ordered_by_diff.insert(make_pair(a[n] - b[n] , n));
	}

	it1 = ordered_by_diff.begin();
	p1 = *it1;
	res[N] = bsum + p1.first;
	a_idx = p1.second;

	long long CASE_I , CASE_II;

	for(int n = N - 1 ; n >= 1 ; n--){
		it1 = ordered_by_b.begin();
	        p1 = *it1;
		if(p1 == make_pair(-b[a_idx] , a_idx))
		    it1++;
		p1 = *it1;
		CASE_I = res[n + 1] + p1.first;
		 

		it2 = ordered_by_diff.begin();
		it2++;
		p2 = *it2;
		CASE_II= res[n + 1] - a[a_idx] + p2.first;

		if(CASE_I < CASE_II){
			res[n] = CASE_I;
			ordered_by_b.erase(p1);
			ordered_by_diff.erase(make_pair(a[p1.second] - b[p1.second] , p1.second));
		}
		else {
			res[n] = CASE_II;
			ordered_by_b.erase(make_pair(-b[a_idx] , a_idx));
			ordered_by_diff.erase(make_pair(a[a_idx] - b[a_idx] , a_idx));
			a_idx = p2.second;
		}
	}
	FAIL:
	for(int n = 1 ; n <= N ; n++)
		printf("%lld\n" , res[n]);
	return 0;
}