oj.uz

Submission #923446

# Submission time Handle Problem Language Result Execution time Memory
923446 2024-02-07T08:52:14 Z heeheeheehaaw Self Study (JOI22_ho_t2) C++17
0 / 100
 1000 ms 6600 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;
    int nr = 0;
    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 = 1, dr = n;
        nr++;
        sort(v + 1, v + n + 1, cmp);
        if(nr >= 100000)
            break;
    }


    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 44 ms 6572 KB Output is correct
3 Correct 46 ms 6600 KB Output is correct
4 Correct 98 ms 6572 KB Output is correct
5 Correct 63 ms 6488 KB Output is correct
6 Correct 103 ms 6568 KB Output is correct
7 Correct 90 ms 6492 KB Output is correct
8 Correct 147 ms 6492 KB Output is correct
9 Execution timed out 1046 ms 6488 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6488 KB Output is correct
2 Incorrect 101 ms 6568 KB Output isn't correct
3 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 44 ms 6572 KB Output is correct
3 Correct 46 ms 6600 KB Output is correct
4 Correct 98 ms 6572 KB Output is correct
5 Correct 63 ms 6488 KB Output is correct
6 Correct 103 ms 6568 KB Output is correct
7 Correct 90 ms 6492 KB Output is correct
8 Correct 147 ms 6492 KB Output is correct
9 Execution timed out 1046 ms 6488 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6488 KB Output is correct
2 Incorrect 101 ms 6568 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 44 ms 6572 KB Output is correct
3 Correct 46 ms 6600 KB Output is correct
4 Correct 98 ms 6572 KB Output is correct
5 Correct 63 ms 6488 KB Output is correct
6 Correct 103 ms 6568 KB Output is correct
7 Correct 90 ms 6492 KB Output is correct
8 Correct 147 ms 6492 KB Output is correct
9 Execution timed out 1046 ms 6488 KB Time limit exceeded
10 Halted 0 ms 0 KB -