Submission #1163590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163590		WongYiKai	Akcija (COCI21_akcija)	C++20	30 / 110	3 ms	328 KiB

Main

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

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll n,k;
    cin >> n >> k;
    pair<ll,ll> item[n+5];
    ll high = 0;
    for (int i=0;i<n;i++){
        ll w,d;
        cin >> w >> d;
        item[i] = {w,d};
        high = max(high,w);
    }
    if (k==1){
        ll mx = 0;
        ll count=0;
        priority_queue<ll,vector<ll>,greater<ll>> pq;
        for (int i=n;i>0;i--){
            for (int j=0;j<n;j++){
                if (item[j].second == i) pq.push(item[j].first);
            }
            if (!pq.empty()){
                count++;
                mx += pq.top();
                pq.pop();
            }
        }
        cout << count << ' ' << mx;
    }
    else if (k==2){
        ll mx = 0;
        ll count=0;
        priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
        ll low[n+5];
        for (int i=0;i<=n;i++){
            low[i] = 0;
        }
        for (int i=n;i>0;i--){
            for (int j=0;j<n;j++){
                if (item[j].second == i) pq.push({item[j].first,j});
            }
            if (!pq.empty()){
                count++;
                mx += pq.top().first;
                for (int j=i;j<=n;j++){
                    low[j] = max(low[j],pq.top().first);
                }
                pq.pop();
            }
        }
        queue<pair<ll,ll>> ans;
        ans.push({count,mx});
        ll mx2 = 2000000000;
        if (pq.empty()){
            ans.push({count-1,mx-high});
        }
        else{
            while (!pq.empty()){
                ll temp = mx;
                ll ind = pq.top().second;
                temp -= low[item[ind].second];
                temp += pq.top().first;
                pq.pop();
                mx2 = min(mx2,temp);
            }
            ans.push({count,mx2});
        }
        while (!ans.empty()){
            cout << ans.front().first << ' ' << ans.front().second << "\n";
            ans.pop();
        }
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 30
• Subtask 6: 0 / 20