시도 횟수: 1회

해결한 시간: 00:43

문제 번역(GPT)

핵심 아이디어

<aside> 💡

$i$스테이지까지 깨는데에 필요한 검의 수를 누적합으로 전처리한다.

$i$번째 칼로 깰 수 있는 스테이지를 이분탐색으로 찾는다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int n;
int a[200'001];
int b[200'001];

void solve()
{
    ll ans = 0LL;

    cin >> n;
    for(int i = 1; i<=n; i++) cin >> a[i];
    for(int i = 1; i<=n; i++) cin >> b[i];

    vector<ll> psum(n+1, 0LL);

    sort(a+1, a+n+1);
    for(int i = 1; i<=n; i++){
        psum[i] = psum[i-1] + b[i];
    }

    for(int i = 1; i<=n; i++){
        int cnt = (n-i+1);
        int clr = upper_bound(psum.begin(), psum.end(), cnt)-psum.begin()-1;

        ans = max(ans, 1LL*a[i]*clr);

        // cout << i <<": " << a[i] <<", " << cnt <<", " << clr <<": "<< ans<<"\\n";
    }
    cout << ans <<"\\n";

    // cout << *lower_bound(psum.begin(), psum.end(), 1);
}

signed main()
{
    FASTIO;
    int _tc; cin >> _tc;
    while (_tc--) solve();
    return 0;
}

복기