pranshu_2004's blog

By pranshu_2004, history, 9 months ago, In English

https://mirror.codeforces.com/contest/2022/problem/B Can anybody tell me that why my sol is not working for above problem

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    int t;
    cin >> t;
    while (t--)
    {
        ll n,x,temp,ans=0;
        cin >> n >> x;
        multiset<ll> s;
        for (int i = 0; i < n; i++)
        {
            cin >> temp;
            s.insert(temp);
        }
        while (s.size()>x)
        {
            vector<ll> p;
            ll j=x,minm=*s.rbegin();
            while (j)
            {
              auto it=s.end();
              it--;
                minm=*it;
                p.push_back(minm);
                s.erase(it);
                j--;
            }
            
            for (int i = 0; i < p.size(); i++)
            {
              if(p[i]-minm!=0)
                s.insert(p[i]-minm);
            }
            ans+=minm;
        }
        if (s.size())
        {
            ans+=*s.rbegin();
        }
        cout << ans << endl;
    }
    return 0;
}
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/blog/entry/135095?#comment-1209182

The code fails on the following test (example)

1

3 2

4 4 3

Optimal strategy:

Get 3 customers to purchase cars 1 and 2: 1 1 3

Get 1 customer to purchase cars 2 and 3: 1 0 2

Get 1 customer to purchase cars 1 and 3: 0 0 1

Get 1 customer to purchase car 3: 0 0 0