Submission #1365788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1365788		biserailieva	Data Centers (EGOI22_datacenters)	C++20	77 / 100	416 ms	9008 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, s;
    cin>>n>>s;
    int A[n];
    for(int i=0;i<n;i++)
    {
        cin>>A[i];
    }
    if(s==0)
    {
        sort(A, A+n);
        reverse(A, A+n);
        for(int i=0;i<n;i++)
        {
            cout<<A[i]<<' ';
        }
        cout<<endl;
    }
    else if(s<=100)
    {
        int c, m;
        for(int i=0;i<s;i++)
        {
            cin>>m>>c;
            sort(A, A+n);
            reverse(A, A+n);
            for(int j=0;j<c;j++)
            {
                A[j]-=m;
            }
        }
        sort(A, A+n);
        reverse(A, A+n);
        for(int i=0;i<n;i++)
        {
            cout<<A[i]<<' ';
        }
        cout<<endl;
    }
    else
    {
        int C[s], M[s];
        bool eden=true;
        for(int i=0;i<s;i++)
        {
            cin>>M[i]>>C[i];
            if(C[i]!=1)
            {
                eden=false;
            }
        }
        if(eden)
        {
            priority_queue<int>pq;
            for(int i=0;i<n;i++)
            {
                pq.push(A[i]);
            }
            for(int i=0;i<s;i++)
            {
                int x=pq.top();
                pq.pop();
                x-=M[i];
                pq.push(x);
            }
            for(int i=0;i<n;i++)
            {
                int x=pq.top();
                pq.pop();
                cout<<x<<' ';
            }
            cout<<endl;
        }
        else
        {
            map<long long, long long>freq;
            for(int i=0;i<n;i++)
            {
                freq[A[i]]++;
            }
            for(int i=0;i<s;i++)
            {
                while(C[i]>0)
                {
                    auto it=prev(freq.end());
                    long long val=it->first;     
                    long long cnt=it->second;
                    freq.erase(it);
                    if(cnt>=C[i])
                    {
                        long long stay = cnt - C[i];
                        long long move = C[i];
                        if(stay > 0) freq[val] += stay;
                        freq[val - M[i]] += move;
                        C[i] = 0;
                    }
                    else
                    {
                        freq[val-M[i]]+=cnt;
                        C[i]-=cnt;
                    }
                }
            }
            vector<long long> res;
            for(auto [val, cnt] : freq)
            {
                for(int i=0;i<cnt;i++) 
                {
                    res.push_back(val);
                }
            }
            sort(res.rbegin(), res.rend());
            for(long long x : res) 
            {
                cout<<x<<' ';
            }
            cout<<endl;
        }
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 26 / 26
• Subtask 5: 18 / 18
• Subtask 6: 0 / 23