Submission #923449

#	Time	Username	Problem	Language	Result	Execution time	Memory
923449		heeheeheehaaw	Self Study (JOI22_ho_t2)	C++17	10 / 100	466 ms	35156 KiB

Main

#include <bits/stdc++.h>
#define int __int128_t

using namespace std;

struct student
{
    int id, sum;
};

int a[300005], b[300005];
student v[300005], init[300005];
int n, m;

bool cmp(student a, student b)
{
    return a.sum < b.sum;
}

bool check(int minn)
{
    for(int i = 1; i <= n; i++)
        v[i] = init[i];

    int st = 1, dr = n;
    while(v[st].sum < minn && st < dr)
    {
        int nev = (minn - v[st].sum);
        int r = nev % b[v[st].id];
        nev /= b[v[st].id];
        if(r != 0) nev++;

        while(dr > st && v[dr].sum >= minn && nev > 0)
        {
            int diff = v[dr].sum - minn;
            int rr = diff % a[v[dr].id];
            diff /= a[v[dr].id];
            if(rr != 0) diff++;

            v[dr].sum -= diff * a[v[dr].id];

            if(diff >= nev)
            {
                v[st].sum += nev * b[v[st].id];
                diff -= nev;
                nev = 0;
                v[dr].sum += diff * a[v[dr].id];
            }
            else
            {
                v[st].sum += diff * b[v[st].id];
                nev -= diff;
                diff = 0;
                dr--;
            }
        }

        st++;
    }

    for(int i = 1; i <= n; i++)
        if(v[i].sum < minn)
            return false;
    return true;
}

signed main()
{
    int64_t aa, bb;
    cin>>aa>>bb;
    n = (int64_t)aa, m = (int64_t)bb;
    for(int i = 1; i <= n; i++)
    {
        cin>>aa;
        a[i] = (int64_t)aa;
    }

    for(int i = 1; i <= n; i++)
    {
        cin>>aa;
        b[i] = (int64_t)aa;
        a[i] = max(a[i], b[i]), init[i].sum = m * a[i], init[i].id = i;
    }


    sort(init + 1, init + n + 1, cmp);
    int st = 0, dr = 1e18, rez;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(check(mij))
            rez = mij, st = mij + 1;
        else dr = mij - 1;
    }

    cout<<(int64_t)rez;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:96:20: warning: 'rez' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     cout<<(int64_t)rez;
      |                    ^~~

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