khuda_ka_banda's blog

By khuda_ka_banda, 5 years ago, In English

Problem c1 POtions of #723 If i put 4 numbers {2,-2,-1,-1} left code gives ans is 3 and right code gives 2 LEft code

int n;
    cin >> n;
    ll arr[n];
    set<pair<ll, int>> s1;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        s1.insert({arr[i], i});
        if (sum < 0)
        {
            pair<ll, int> p = *s1.begin();
            sum -= p.ff;
            s1.erase(p);
        }
    }
    cout << size(s1) << newline;

Right code

int n;
    cin >> n;
    ll arr[n];
    set<int> s1;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        s1.insert(arr[i]);
        if (sum < 0)
        {

            sum -= *s1.begin();
            s1.erase(s1.begin());
        }
    }
    cout << sz(s1) << nline;
  • Vote: I like it
  • -13
  • Vote: I do not like it

| Write comment?
»
5 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Set does not take duplicate elements so when you are using pair all elements are unique because of their indexes but when you are just using set duplicate elements are not there in the set therefore result is different