oj.uz

Submission #923066

# Submission time Handle Problem Language Result Execution time Memory
923066 2024-02-06T14:04:45 Z heeheeheehaaw Self Study (JOI22_ho_t2) C++17
10 / 100
 286 ms 21072 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++;
    }

    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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 271 ms 20296 KB Output is correct
12 Correct 284 ms 20068 KB Output is correct
13 Correct 226 ms 18256 KB Output is correct
14 Correct 283 ms 18256 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 245 ms 15516 KB Output is correct
17 Correct 286 ms 21072 KB Output is correct
18 Correct 274 ms 20304 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 245 ms 15516 KB Output is correct
3 Correct 286 ms 21072 KB Output is correct
4 Correct 274 ms 20304 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 271 ms 20296 KB Output is correct
12 Correct 284 ms 20068 KB Output is correct
13 Correct 226 ms 18256 KB Output is correct
14 Correct 283 ms 18256 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 271 ms 20296 KB Output is correct
12 Correct 284 ms 20068 KB Output is correct
13 Correct 226 ms 18256 KB Output is correct
14 Correct 283 ms 18256 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -