Submission #534128

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
534128	2022-03-08T01:23:48 Z	Paul_Liao_1457	Self Study (JOI22_ho_t2)	C++17	0 / 100	414 ms	5036 KB

Main

// 還要更強
#include<iostream>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<math.h>
#include<cstring>
#include<stack>
#include<string.h>
#include<random>
#include<algorithm>
#include<vector>

#define ll long long
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define INF (ll)(2e18)
#define pb push_back
#define F first
#define S second

using namespace std;

ll n,m;
ll A[300005],B[300005];

bool check(ll x){
    ll res=0;
    FOR(i,0,n){
        ll tmp=x;
        if((A[i]*m)<=tmp){
            tmp-=1ll*(A[i]*m);
            if(tmp<0){
                tmp=0;
            }
            else if(tmp>0){
                tmp=(tmp-1)/abs(B[i])+1;
            }
            res-=tmp;
        }
        else{
            ll used=max(1ll,(tmp-1)/abs(A[i])+1);
            res+=m-used;
        }
    }
    if(res>=0) return 1;
    return 0;
}

signed main(){
    cin>>n>>m;
    FOR(i,0,n){
        cin>>A[i];
    }
    FOR(i,0,n){
        cin>>B[i]; A[i]=max(A[i],B[i]);
    }
    ll l=0,r=(1e18+1),ans=0;
    while(l<r){
        ll mid=(l+r)>>1;
        if(check(mid)){
            ans=max(ans,mid); l=mid+1;
        }
        else{
            r=mid;
        }
    }
    cout<<ans<<endl;
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	6 ms	376 KB	Output is correct
11	Correct	321 ms	4968 KB	Output is correct
12	Correct	316 ms	4904 KB	Output is correct
13	Correct	256 ms	4964 KB	Output is correct
14	Incorrect	414 ms	5036 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 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	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	164 ms	2580 KB	Output is correct
10	Correct	111 ms	1844 KB	Output is correct
11	Correct	80 ms	1444 KB	Output is correct
12	Correct	64 ms	1160 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Incorrect	6 ms	332 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	6 ms	376 KB	Output is correct
11	Correct	321 ms	4968 KB	Output is correct
12	Correct	316 ms	4904 KB	Output is correct
13	Correct	256 ms	4964 KB	Output is correct
14	Incorrect	414 ms	5036 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 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	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	164 ms	2580 KB	Output is correct
10	Correct	111 ms	1844 KB	Output is correct
11	Correct	80 ms	1444 KB	Output is correct
12	Correct	64 ms	1160 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	0 ms	204 KB	Output is correct
16	Correct	0 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Incorrect	6 ms	332 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	6 ms	376 KB	Output is correct
11	Correct	321 ms	4968 KB	Output is correct
12	Correct	316 ms	4904 KB	Output is correct
13	Correct	256 ms	4964 KB	Output is correct
14	Incorrect	414 ms	5036 KB	Output isn't correct
15	Halted	0 ms	0 KB	-