답안 #534074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
534074	2022-03-08T00:28:26 Z	balbit	Self Study (JOI22_ho_t2)	C++14	0 / 100	909 ms	10716 KB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)

#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<" - ", _do(__VA_ARGS__)
template <typename T> void _do( T && x) {cerr<<x<<endl;}
template <typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 3e5+5;

ll a[maxn], b[maxn];
int n,m;
bool can(ll X) {
    ll pool = 0;
    REP(i,n) {

        ll keep = min(X / a[i], m);
        ll need = (X - a[i] * keep + b[i]-1) / b[i];

        ll g1 = m-keep-need;

        keep = min((X+a[i]-1) / a[i], m);
        need = (max(0ll, X - a[i] * keep)
                 + b[i]-1) / b[i];
        ll g2 = m-keep-need;
        pool += max(g1, g2);
        bug(i, g1, g2);
    }

    bug(X, pool);
    return pool >= 0;
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);

    bug(1,2);
    cin>>n>>m;

    REP(i,n) cin>>a[i];
    REP(i,n) cin>>b[i], MX(a[i], b[i]);

    ll l = 0, r = 2e18;
    while (l!=r) {
        ll mid = (l+r)/2;
        if (can(mid)) {
            l = mid+1;
        }else{
            r = mid;
        }
    }
    cout<<l-1<<endl;
}

Subtask #1

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	320 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	8 ms	460 KB	Output is correct
11	Correct	485 ms	10716 KB	Output is correct
12	Correct	488 ms	10712 KB	Output is correct
13	Correct	478 ms	8772 KB	Output is correct
14	Incorrect	909 ms	8784 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	320 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	251 ms	5568 KB	Output is correct
10	Correct	166 ms	3804 KB	Output is correct
11	Correct	124 ms	2884 KB	Output is correct
12	Correct	101 ms	2408 KB	Output is correct
13	Correct	2 ms	332 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	1 ms	320 KB	Output is correct
18	Incorrect	18 ms	416 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	320 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	8 ms	460 KB	Output is correct
11	Correct	485 ms	10716 KB	Output is correct
12	Correct	488 ms	10712 KB	Output is correct
13	Correct	478 ms	8772 KB	Output is correct
14	Incorrect	909 ms	8784 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	320 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	251 ms	5568 KB	Output is correct
10	Correct	166 ms	3804 KB	Output is correct
11	Correct	124 ms	2884 KB	Output is correct
12	Correct	101 ms	2408 KB	Output is correct
13	Correct	2 ms	332 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	1 ms	320 KB	Output is correct
18	Incorrect	18 ms	416 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	320 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	8 ms	460 KB	Output is correct
11	Correct	485 ms	10716 KB	Output is correct
12	Correct	488 ms	10712 KB	Output is correct
13	Correct	478 ms	8772 KB	Output is correct
14	Incorrect	909 ms	8784 KB	Output isn't correct
15	Halted	0 ms	0 KB	-