Submission #612372

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
612372	2022-07-29T13:40:09 Z	boris_mihov	Self Study (JOI22_ho_t2)	C++14	0 / 100	514 ms	10764 KB

Main

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 300000 + 10;
const llong INF = 2e18;

llong n, m;
llong a[MAXN], b[MAXN];
llong achieved[MAXN];

bool check(llong value)
{
    llong freeB = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (b[i] >= a[i])
        {
            llong currLections = (value / b[i] + ((value % b[i]) > 0));
            freeB += m - currLections;
        } else
        {
            llong currLections = std::min(m, (value / a[i] + ((value % a[i]) > 0)));
            if (currLections < m) freeB += m - currLections;
            else
            {
                llong moreLections = std::max(0LL, ((value - m * a[i]) / b[i] + (((value - m * a[i]) % b[i]) > 0)));
                freeB -= moreLections;
            }
        }
    }

    return freeB >= 0;
}

void solve()
{
    llong l = 0, r = INF, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    std::cout << l << '\n';
}

void read()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= n ; ++i) std::cin >> a[i];
    for (int i = 1 ; i <= n ; ++i) std::cin >> b[i];
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	304 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	4 ms	424 KB	Output is correct
11	Correct	236 ms	10756 KB	Output is correct
12	Correct	236 ms	10764 KB	Output is correct
13	Correct	162 ms	8816 KB	Output is correct
14	Incorrect	514 ms	8820 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	97 ms	5568 KB	Output is correct
10	Correct	66 ms	3808 KB	Output is correct
11	Correct	46 ms	2948 KB	Output is correct
12	Correct	35 ms	2424 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	324 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Incorrect	5 ms	392 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	304 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	4 ms	424 KB	Output is correct
11	Correct	236 ms	10756 KB	Output is correct
12	Correct	236 ms	10764 KB	Output is correct
13	Correct	162 ms	8816 KB	Output is correct
14	Incorrect	514 ms	8820 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	97 ms	5568 KB	Output is correct
10	Correct	66 ms	3808 KB	Output is correct
11	Correct	46 ms	2948 KB	Output is correct
12	Correct	35 ms	2424 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	324 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Incorrect	5 ms	392 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	304 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	4 ms	424 KB	Output is correct
11	Correct	236 ms	10756 KB	Output is correct
12	Correct	236 ms	10764 KB	Output is correct
13	Correct	162 ms	8816 KB	Output is correct
14	Incorrect	514 ms	8820 KB	Output isn't correct
15	Halted	0 ms	0 KB	-