結果

問題 No.3537 Thank You!
コンテスト
ユーザー ZeriToki
提出日時 2026-05-08 21:57:57
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 2,086 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,436 ms
コンパイル使用メモリ 336,708 KB
実行使用メモリ 6,912 KB
最終ジャッジ日時 2026-05-08 21:58:09
合計ジャッジ時間 4,879 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サブタスク1 30 % AC * 21
サブタスク2 70 % AC * 15
合計 2.5 * 100% = 250 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const long long mod=998244353;
const long long mod2=469762049;
int main(){
    cout.tie()->sync_with_stdio(0);
    cin.tie(0);
    int N;cin>>N;
    ll B;cin>>B;
    pair<ll,ll>C[N+1];
    for(int i=1;i<=N;i++) cin>>C[i].first;
    for(int i=1;i<=N;i++) cin>>C[i].second;
    sort(C+1,C+N+1);
    /*for(int i=1;i<=N;i++) cout<<C[i].first<<" ";
    cout<<endl;
    for(int i=1;i<=N;i++) cout<<C[i].second<<" ";
    cout<<endl;*/
    ll ruiseki[N+1],cnt[N+1];
    ruiseki[0]=0;
    cnt[0]=0;
    for(int i=1;i<=N;i++){
        ruiseki[i]=C[i].first*C[i].second;
        ruiseki[i]+=ruiseki[i-1];
        cnt[i]=C[i].second;
        cnt[i]+=cnt[i-1];
    }
    ll ans=0;
    for(int i=1;i<=N;i++){
        ll now=0;
        ll now_B=B-C[i].second;
        if(now_B<0){
            ans=B;
            break;
        }
        now+=C[i].second;
        if(ruiseki[i-1]<=now_B){
            now+=cnt[i-1];
            now_B-=ruiseki[i-1];
            auto iter=upper_bound(ruiseki+i+1,ruiseki+N+1,now_B+ruiseki[i]);
            int idx=distance(ruiseki,iter);
            idx--;
            assert(idx>=0);
            now_B-=(ruiseki[idx]-ruiseki[i]);
            now+=cnt[idx]-cnt[i];
            idx++;
            if(idx<=N){
                now+=now_B/C[idx].first;
            }
            chmax(ans,now);
            //cout<<i<<" "<<idx<<" "<<now<<endl;
        }
        else{
            auto iter=upper_bound(ruiseki,ruiseki+N+1,now_B);
            int idx=distance(ruiseki,iter);
            idx--;
            assert(idx>=0);
            now_B-=ruiseki[idx];
            now+=cnt[idx];
            idx++;
            if(idx<=N){
                now+=now_B/C[idx].first;
            }
            chmax(ans,now);
            //cout<<now<<endl;
        }
    }
    cout<<ans<<endl;
}
0