Submission #532657

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
532657	2022-03-03T14:53:44 Z	victor_gao	Self Study (JOI22_ho_t2)	C++17	0 / 100	327 ms	10716 KB

Main

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 300015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int a[N],b[N],n,m;
bool check(int val){
	int cnt=0;
	for (int i=1;i<=n;i++){
		if (a[i]>b[i]){
			if (a[i]*m<val){
				cnt+=m;
				int newval=val-a[i]*m;
				cnt+=(newval/b[i]+(newval%b[i]>0)); 
			}
			else cnt+=(val/a[i]+(val%a[i]>0));
		}
		else {
			cnt+=(val/b[i]+(val%b[i]>0));
		}
	}
	return cnt<=m*n;
}
signed main(){
	fast
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=n;i++) cin>>b[i];
	int l=0,r=1e18;
	while (l<r){
		int mid=(l+r)>>1;
		if (check(mid)) l=mid+1;
		else r=mid;
	}
	cout<<l-1<<'\n';
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	332 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	3 ms	460 KB	Output is correct
11	Correct	183 ms	10716 KB	Output is correct
12	Correct	186 ms	10708 KB	Output is correct
13	Correct	161 ms	8744 KB	Output is correct
14	Incorrect	327 ms	8736 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	332 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	88 ms	5492 KB	Output is correct
10	Correct	57 ms	3804 KB	Output is correct
11	Correct	50 ms	2892 KB	Output is correct
12	Correct	37 ms	2312 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	328 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Incorrect	5 ms	336 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	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	332 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	3 ms	460 KB	Output is correct
11	Correct	183 ms	10716 KB	Output is correct
12	Correct	186 ms	10708 KB	Output is correct
13	Correct	161 ms	8744 KB	Output is correct
14	Incorrect	327 ms	8736 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	332 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	88 ms	5492 KB	Output is correct
10	Correct	57 ms	3804 KB	Output is correct
11	Correct	50 ms	2892 KB	Output is correct
12	Correct	37 ms	2312 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	328 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Incorrect	5 ms	336 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	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	332 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	3 ms	460 KB	Output is correct
11	Correct	183 ms	10716 KB	Output is correct
12	Correct	186 ms	10708 KB	Output is correct
13	Correct	161 ms	8744 KB	Output is correct
14	Incorrect	327 ms	8736 KB	Output isn't correct
15	Halted	0 ms	0 KB	-