oj.uz

Submission #923445

# Submission time Handle Problem Language Result Execution time Memory
923445 2024-02-07T08:51:04 Z heeheeheehaaw Self Study (JOI22_ho_t2) C++17
10 / 100
 393 ms 14740 KB 
#include <bits/stdc++.h>
#define int long long

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++;
    }

    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()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    for(int i = 1; i <= n; i++)
        cin>>b[i], 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<<rez;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6744 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 6 ms 6492 KB Output is correct
11 Correct 331 ms 14712 KB Output is correct
12 Correct 324 ms 14416 KB Output is correct
13 Correct 300 ms 14676 KB Output is correct
14 Correct 393 ms 14416 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 392 ms 14500 KB Output is correct
17 Correct 356 ms 14416 KB Output is correct
18 Correct 332 ms 14740 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 392 ms 14500 KB Output is correct
3 Correct 356 ms 14416 KB Output is correct
4 Correct 332 ms 14740 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Incorrect 1 ms 6492 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6744 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 6 ms 6492 KB Output is correct
11 Correct 331 ms 14712 KB Output is correct
12 Correct 324 ms 14416 KB Output is correct
13 Correct 300 ms 14676 KB Output is correct
14 Correct 393 ms 14416 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Incorrect 1 ms 6492 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6744 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 6 ms 6492 KB Output is correct
11 Correct 331 ms 14712 KB Output is correct
12 Correct 324 ms 14416 KB Output is correct
13 Correct 300 ms 14676 KB Output is correct
14 Correct 393 ms 14416 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Incorrect 1 ms 6492 KB Output isn't correct
17 Halted 0 ms 0 KB -