답안 #923065

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923065 2024-02-06T14:04:30 Z heeheeheehaaw Self Study (JOI22_ho_t2) C++17
0 / 100
0 ms 348 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 = 36, 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;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -