2019 KCPC faith

2019 KCPC 신앙 (신입생 부문 G번 / 일반 부문 C번) 코드 제출 url

그리디 문제입니다. 이 문제를 풀기 위해서는 중요한 아이디어 하나를 생각해 내야 합니다.

누구를 선택하는게 최선인지는 모르지만, 어느 한 명을 선택하여 빨간약을 몰아주는 것이 최선일 것입니다. 체력이 다른 두 사람$ (x,y) $이 있다고 가정합시다. $ x<y $ 라고 했을 때, 약을 나누어 주는 것보단 당연히 y에게 몰아주는 것이 효율적일 것입니다.

이제 나머지는 구현입니다. 파란약이 없다고 가정하고 헌금 금액을 구한 후에, 우선 순위 큐 등을 사용하여 (파란약을 사용했을 경우 얻는 이득)을 파란 병의 개수에 맞게 최대화 시킵니다.

모든 사람에게 빨간약을 몰아줘 보고 최대값을 구한다고 한다면 시간복잡도는 $ Nlog(N) $ 이 됩니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int SZ=1005;
pii arr[SZ];
int main(void){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll n,r,b; cin>>n>>r>>b;
    for(int i=1;i<=n;i++){
        ll a,b; cin>>a>>b;
        arr[i]={a,b};
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        priority_queue<ll> pq;
        ll tmp=0;
        for(int j=1;j<=n;j++){
            if(j==i) pq.push((arr[j].first<<r)-arr[j].second);
            else pq.push(arr[j].first-arr[j].second);
            tmp+=arr[j].second;
        }
        int bb=b;
        while(bb-- && !pq.empty() && pq.top()>0){
            tmp+=pq.top(); pq.pop();
        }
        ans=max(ans,tmp);
    }
    cout<<ans;
    return 0;
}