oj.uz

Submission #923449

# Submission time Handle Problem Language Result Execution time Memory
923449 2024-02-07T09:00:12 Z heeheeheehaaw Self Study (JOI22_ho_t2) C++17
10 / 100
 466 ms 35156 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 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 2 ms 6488 KB Output is correct
10 Correct 5 ms 6748 KB Output is correct
11 Correct 460 ms 34472 KB Output is correct
12 Correct 441 ms 34388 KB Output is correct
13 Correct 386 ms 32652 KB Output is correct
14 Correct 378 ms 32276 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Correct 410 ms 29648 KB Output is correct
17 Correct 423 ms 35156 KB Output is correct
18 Correct 466 ms 34388 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 410 ms 29648 KB Output is correct
3 Correct 423 ms 35156 KB Output is correct
4 Correct 466 ms 34388 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Incorrect 2 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 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 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 2 ms 6488 KB Output is correct
10 Correct 5 ms 6748 KB Output is correct
11 Correct 460 ms 34472 KB Output is correct
12 Correct 441 ms 34388 KB Output is correct
13 Correct 386 ms 32652 KB Output is correct
14 Correct 378 ms 32276 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Incorrect 2 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 2 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 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6488 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 2 ms 6488 KB Output is correct
10 Correct 5 ms 6748 KB Output is correct
11 Correct 460 ms 34472 KB Output is correct
12 Correct 441 ms 34388 KB Output is correct
13 Correct 386 ms 32652 KB Output is correct
14 Correct 378 ms 32276 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct
16 Incorrect 2 ms 6492 KB Output isn't correct
17 Halted 0 ms 0 KB -