백준 3131번 크리스마스 선물

🔒문제 url

https://www.acmicpc.net/problem/3131

🪄전체 코드

#include <iostream>
#include <algorithm>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);

typedef long long ll;
ll a,b;
int n;
ll price[100005];
ll evenPs[100005];
ll oddPs[100005];
ll total = 0;
vector<pair<ll,ll>> range;

void INPUT()
{
    IAMFAST
    cin >> a >> b >> n;
    for(int i = 1; i < n; i++)
    {
        cin >> price[i];
        total += price[i];
        if(i % 2) oddPs[i] = oddPs[max(0,i-2)] + price[i];
    }
}

pair<ll,ll> getPrice(int idx)
{
    ll old, young;
    if(idx % 2) old = oddPs[max(0,idx-2)]+evenPs[idx+1];
    else old = oddPs[idx-1]+evenPs[idx];
    young = total - old;
    return {old,young};
}

pair<ll,ll> getRange(int idx, ll gap)
{
    ll left, right;
    if(idx % 2) left = a-gap, right = b-gap;
    else left = -(b-gap), right = -(a-gap);
    return {left,right};
}

ll setAns()
{
    ll ans = 0;
    sort(range.begin(), range.end());

    ll right = -1;
    for (auto &r : range)
    {
        if(right < r.first)
        {
            ans += r.second - r.first + 1;
            right = r.second;
        }
        else if(right < r.second)
        {
            ans += r.second - right;
            right = r.second;
        }
    }
    return ans;
}

void adjustRange(int idx, ll &left, ll &right)
{
    ll leftLine,rightLine;
    if(idx == 1)
    {
        leftLine = price[1];
        rightLine = 10e9;
    }
    else if(idx == n)
    {
        leftLine = 1;
        rightLine = price[n-1];
    }
    else
    {
        leftLine = price[idx];
        rightLine = price[idx-1];
    }

    left = max(leftLine, left);
    right = min(rightLine, right);
}

void SOLVE()
{
    for(int i = (n%2) ? n-1 : n-2; i >= 1; i-=2)
        evenPs[i] = evenPs[i+2] + price[i];


    for(int i = 1; i <= n; i++)
    {
        auto [old, young] = getPrice(i);

        auto [left,right] = getRange(i, old-young);

        adjustRange(i,left,right);
        if(left > right) continue;

        range.emplace_back(left, right);
    }

    cout << setAns();
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

맞왜틀 2시간 끝에 겨우겨우 성공..
adjustRange()의 필요성을 뒤늦게야 깨달았다.🥲
Platinum은 하나 풀려면 6시간(실제로는 덜 걸리더라도) 쓸 각오로 덤벼야하는 내가 너무 하찮다!😭
그런데 사실 이런 문제보다, Gold 상위 빡구현 문제가 몇 배로 힘들다.