# Help In Potions(HARD) Codeforces Round #723

Please Explain Full Solution Or Just Tell Which Algorithm To Apply
Question Link: Problem - C2 - Codeforces
My Approach: 1 Like

Learn about heaps, I think that’s the easiest way to approach this problem.

CODE
``````#include "bits/stdc++.h"
using namespace std ;
int main(){
long long n,s=0,ans=0;cin >> n ;
vector<int>a(n) ;
for(int &x:a)
cin >> x  ;
priority_queue<int>pq ;
for(int i=0;i<n;i++){
s+=a[i],ans++ ;
pq.push(-a[i]) ;
if(s<0)
s+=pq.top(),pq.pop(),--ans  ;
}
cout << ans ;
}
``````
2 Likes

Use greedy
Run a loop
Keep a variable which stores sum and keep adding no.s to it.
Store negative no.s in a set. Whenever sum gets less than 0 add greatest absolute value from set.

1 Like

Thanks @cubefreak777, @pie_3

1 Like
``````package com.codeforces;

import java.util.Arrays;
import java.util.Scanner;

public class PotionsEasy {
public static void main(String[] args){
Scanner scin = new Scanner(System.in);
int t = scin.nextInt();
int[] a = new int[t];
for (int i = 0; i < t; i++) {
a[i] = scin.nextInt();
}
Arrays.sort(a);
int current_count = 0;
int count = 0;
for (int i = a.length - 1; i >= 0; i--) {
current_count+=a[i];
if (current_count<0){
current_count+=Math.abs(a[i]);
}
else {
count++;
}
}
System.out.println(count);
}
}
``````

I think you are saying this

1 Like

@cubefreak777 Yes I Will, Could You PLEASE Share Any Article Or Some Site URL On HEAPS

2 Likes

By heaps, I meant to say that you should at least be able to use the built-in PriorityQueues, like what are its properties, when to use it, other methods of PriorityQueue, etc… , though if you want to learn the actual working of priority queues(heaps) then you can check this

1 Like

Thanks @cubefreak777, Yes I Want To Learn Actual Working, The Tutorial You shared Is very Nice

2 Likes