Submission #1041229

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1041229	2024-08-01T18:29:44 Z	SoulKnight	Self Study (JOI22_ho_t2)	C++17	0 / 100	115 ms	5076 KB

Main

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ln '\n'

const int N = 3e5 + 5;
const ll INF = 1e18 + 5;

ll n, m, a[N], b[N];
inline ll ceil(ll x, ll y) {
    return (x + y - 1) / y;
}

ll cnt(ll go_lesson, ll i, ll tar){
    return (m - go_lesson) - max(0LL, ceil(tar - a[i] * go_lesson, b[i]));
}

void solve(){
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    // ll l = 7, r = 7, ans = 0;
    ll l = 0, r = INF, ans = 0;
    while (l <= r){
        ll tar = (l + r) / 2;
        ll diff = 0; // diff = free - need

        for (int i = 0; i < n; i++){
            diff += max(cnt(1, i, tar), cnt(0, i, tar));
        }
        if (diff >= 0) {ans = tar; l = tar + 1;}
        else r = tar - 1;
    }
    cout << ans << ln;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // int TT; cin >> TT;
    // while (TT--) {solve();}

    solve();

}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	1 ms	2648 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	103 ms	5076 KB	Output is correct
12	Correct	104 ms	4952 KB	Output is correct
13	Correct	94 ms	4956 KB	Output is correct
14	Incorrect	115 ms	4956 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	2396 KB	Output is correct
2	Correct	0 ms	2392 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	51 ms	4696 KB	Output is correct
10	Correct	35 ms	4700 KB	Output is correct
11	Correct	26 ms	4748 KB	Output is correct
12	Correct	22 ms	4700 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	1 ms	2392 KB	Output is correct
15	Correct	0 ms	2396 KB	Output is correct
16	Correct	0 ms	2396 KB	Output is correct
17	Correct	0 ms	2396 KB	Output is correct
18	Incorrect	2 ms	2396 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	2392 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	1 ms	2648 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	103 ms	5076 KB	Output is correct
12	Correct	104 ms	4952 KB	Output is correct
13	Correct	94 ms	4956 KB	Output is correct
14	Incorrect	115 ms	4956 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	2396 KB	Output is correct
2	Correct	0 ms	2392 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	0 ms	2396 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	51 ms	4696 KB	Output is correct
10	Correct	35 ms	4700 KB	Output is correct
11	Correct	26 ms	4748 KB	Output is correct
12	Correct	22 ms	4700 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	1 ms	2392 KB	Output is correct
15	Correct	0 ms	2396 KB	Output is correct
16	Correct	0 ms	2396 KB	Output is correct
17	Correct	0 ms	2396 KB	Output is correct
18	Incorrect	2 ms	2396 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	2392 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	1 ms	2648 KB	Output is correct
9	Correct	0 ms	2396 KB	Output is correct
10	Correct	2 ms	2396 KB	Output is correct
11	Correct	103 ms	5076 KB	Output is correct
12	Correct	104 ms	4952 KB	Output is correct
13	Correct	94 ms	4956 KB	Output is correct
14	Incorrect	115 ms	4956 KB	Output isn't correct
15	Halted	0 ms	0 KB	-