Submission #923754

#	Time	Username	Problem	Language	Result	Execution time	Memory
923754		Amr	Self Study (JOI22_ho_t2)	C++14	100 / 100	379 ms	12216 KiB

Main

#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define all(x) (x).begin(),(x).end()
#define sz size()
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define pb(x) push_back(x);
#define endl '\n'
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N=3e5+7;
ll INF=INT_MAX,mod=1e9+7;
int TT=1;
ll power(ll x, unsigned int y)
{
    ll res = 1;
    x = x; // % mod;
    if (x == 0) return 0;
    while (y > 0)
    {
        if (y & 1) res = (res*x)  ; // % mod;
        y = y>>1;
        x = (x*x) ; // % mod;
    }
    return res;
}
ll n , m;
ll a1[N],a2[N];
pair<ll,ll> b[N];
ll cnt[N];
bool good(ll mid)
{
    memset(cnt,0,sizeof cnt);
    ll garbge = 0;
    for(int i = 1; i <= n; i++)
    {
        ll cur = b[i].S;
        ll mx = b[i].F;
        cnt[cur] += m*mx;

        if(cnt[cur]==mid) continue;
        if(cnt[cur]>mid)
        {
            ll dif = cnt[cur]-mid;
            garbge+=(dif/mx);
            cnt[cur] -= (dif/mx)*mx;
        }
        else
        {
            ll dif = mid-cnt[cur];
            ll o = ((dif+a2[cur]-1)/a2[cur]);
            garbge-=o;
            if(garbge<0) return 0;
        }
    }
    return 1;
}
void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a1[i];
    for(int i = 1; i <= n; i++) cin >> a2[i];
    for(int i = 1; i <= n; i++) {b[i].F = max(a1[i],a2[i]); b[i].S=i;}
    sort(b+1,b+1+n,greater<pair<ll,ll> >());
    ll l = 0, r = 1;
    while(good(r)) r*=2;
    //cout << good(18) << endl; return;
    while(l+1<r)
    {
        ll mid = (l+r)/2;
        if(good(mid)) l = mid; else r = mid;
    }
    cout << l << endl;
}
int main(){
    //freopen("friday.in","r",stdin);
    //freopen("friday.out","w",stdout);
    fast;
        while(TT--)
        solve();

    return 0;
}

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