세균 번식 (JUNGOL 8679)

https://jungol.co.kr/problem/8679

---

아이디어

행은 최대 4000개입니다. 그러므로 각 행마다 그 행에서 가장 늦게 번식되는 위치를 찾아주면 됩니다.

 

각 행마다 가장 먼저 번식되는 위치는 모든 세균의 열이라고 할 수 있습니다. 그러므로 그 열의 위치에 번식되는 시각을 표시해줍시다. 그런데 만약 서로 d만큼 차이나는 두 열에서의 번식 시각이 d보다 크게 차이가 난다면 더 큰쪽을 작은쪽+d로 맞추어주면 됩니다.

 

그러면 O(K)에 가장 늦게 번식되는 위치를 찾아줄 수 있습니다. 이것을 각 행마다 시행해주면 O(NK)에 문제를 해결할 수 있습니다.

---

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define ll long long
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,M,K,i,x,y;
    vector <pair <ll,ll> > germ;

    cin>>N>>M>>K;
    for (i=0;i<K;i++)
    {
        cin>>x>>y;
        germ.push_back({x,y});
    }

    ll Ans=0;
    for (i=1;i<=N;i++)
    {
        vector <pair <ll,ll> > germ2; //{도착 위치, 도착 시각}
        for (ll j=0;j<K;j++)
            germ2.push_back({germ[j].second,abs(germ[j].first-i)});

        sort (germ2.begin(),germ2.end());
        for (ll j=1;j<K;j++)
            germ2[j].second=min(germ2[j].second,germ2[j-1].second+(germ2[j].first-germ2[j-1].first));
        for (ll j=K-2;j>=0;j--)
            germ2[j].second=min(germ2[j].second,germ2[j+1].second+(germ2[j+1].first-germ2[j].first));

        Ans=max({Ans,germ2[0].first+germ2[0].second-1,(M-germ2[K-1].first)+germ2[K-1].second});
        for (ll j=0;j<K-1;j++)
            Ans=max(Ans,(germ2[j].second+germ2[j+1].second+(germ2[j+1].first-germ2[j].first))/2);
    }

    cout<<Ans;
}