CF 986 problem C 풀이 정리

버츄얼 돌다 만난 문제. 투포인터랑 부분합을 더 많이 풀어봐야겠다는 생각이 들었다.

 

일단 버츄얼 중에는 B를 만나고 멘탈에 많은 타격이 들어와 슼보를 왔다갔다 하며

 

C를 풀까말까 했다. 결국 B와 C 모두 풀지 못했다.

 

문제 핵심 아이디어

$pfx$ 배열의 단조성을 이용하여 이분탐색 or 투포인터를 사용해야한다.

 

일단 m개의 creature에게 분배될 수 있는지부터 확인해야 하기 때문에

 

이를 관리해주어야 한다.

 

$pfx[i]$를 앞에서부터 $i$ 까지 봤을 때 분배해줄 수 있는 creature 수라고 하고

 

$sfx[i]$를 뒤에서부터 $i$ 까지 봤을 때 분배해줄 수 있는 creature 수라고 하자. 

 

이는 투포인터로 연속된 구간의 합을 합/차 해가며 그리디하게 $pfx$ 배열에 기록해주면 된다.

 

포인터 $start$에 따른 $end$를 구간 합이 작을 동안 증가시키고 가능한 경우라면 $start$에서 올 수 있게 기록하면 된다.

 

이때 $pfx[end]$ 값을 그리디하게 선택해야하기 때문에 $start$ 포인터를 for문으로 관리해준다.

 

그리고 마지막에서도 투포인터가 사용되는데

 

각 $pfx[i]+sfx[j]>=m$을 만족하는 $j$의 최댓값을 구해주고 $[i+1,j-1]$까지를 Alice에게 주면 된다.

 

따라서 for문으로 $i$를 증가시키면서 최대 $j$ 값을 찾고 그때 Alice가 얻을 수 있는 양을 구해주면 된다. 

 

코드는 다음과 같다.

 

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int main(){

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int t;

    cin >> t;

    while(t--){

        int n,m;

        ll v;

        cin >> n >> m >> v;

        vector<ll> a(n),sum(n+1,0);

        for(int i=0;i<n;i++){

            cin >> a[i];

            sum[i+1]=sum[i]+a[i];

        }

        auto solve=[&]() -> vector<int> {

            vector<int> pfx(n+1,0);

            int e=0;

            ll rsum=0;

            for(int s=0;s<n;s++){

                while(e<n && rsum<v){

                    rsum+=a[e];

                    e++;

                    pfx[e]=max(pfx[e],pfx[e-1]);

                }

                if(rsum>=v) pfx[e]=pfx[s]+1;

                rsum-=a[s];

            }

            for(int i=1;i<=n;i++) pfx[i]=max(pfx[i],pfx[i-1]);

            return pfx;

        };

        auto getsum=[&](int a, int b){ return sum[b]-sum[a]; };

        auto pfx=solve();

        if(pfx[n]<m){

            cout << "-1\n";

            continue;

        }

        reverse(a.begin(),a.end());

        auto sfx=solve();

        reverse(sfx.begin(),sfx.end());

        int e=0;

        ll ans=0;

        for(int s=0;s<n;s++){

            while(e<n && pfx[s]+sfx[e+1]>=m) e++;

            if(pfx[s]+sfx[e]>=m) ans=max(ans,getsum(s,e));

        }

        cout << ans << '\n';

    }

    return 0;

}