Submission #534153

#	Time	Username	Problem	Language	Result	Execution time	Memory
534153		Cookie197	Self Study (JOI22_ho_t2)	C++14	100 / 100	261 ms	10632 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll> 
#define mp make_pair
#define endl "\n"
#define out(x) cout << #x << " = " << x << endl
#define outp(x) cout << #x << ".first = " << x.first << "  " << #x << ".second = " << x.second << endl
#pragma GCC optimize("Ofast")
#define lll __int128

ll n,m;
ll a[300005],b[300005];
signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++) { ll x; cin>>x; a[i] = x;}
    for (int i=1;i<=n;i++) { ll x; cin>>x; b[i] = x; a[i] = max(a[i], b[i]);}
    if (m==1){
        ll ans = 1e18;
        for (int i=1;i<=n;i++) ans = min(ans, max(a[i],b[i]));
        cout<<(ll)ans<<endl;
        return 0;
    }

    ll arr[n+2], remain[n+2];  // 目前學分，這個位置剩下幾堂課
    ll left = 0, right = 2e18, mid = (left+right)/2;
    while(left<right){
        mid = (left+right)/2;
        ll rem=0;
        int flag=true;
        for (int i=1;i<=n;i++) {
            if (a[i] * m < mid) {
                arr[i] = a[i] * m;
            }else{
                ll use = (mid-1)/a[i] + 1;
                rem += m - use;
                arr[i] = use * a[i];
            }
        }
        //cout<<mid<<"  "<<rem<<endl;
        for (int i=1;i<=n;i++) if (arr[i]<mid){
            ll need = (mid-arr[i]-1) / b[i] + 1;
            rem -= need;
            if (rem<0) {flag=false; break;}
        }
        if (flag) left=mid+1;
        else right=mid;
    }
    cout<<(ll)left-1<<endl;

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:29:18: warning: unused variable 'remain' [-Wunused-variable]
   29 |     ll arr[n+2], remain[n+2];  // 目前學分，這個位置剩下幾堂課
      |                  ^~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 9 / 9