oj.uz

Submission #923967

# Submission time Handle Problem Language Result Execution time Memory
923967 2024-02-08T07:05:53 Z Xiaoyang Self Study (JOI22_ho_t2) C++17
0 / 100
 424 ms 5408 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 1ll<<60
#define rep(i,a,b) for (ll i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
#define endl "\n"
void inc(ll &a,ll b) {a=(a+b)%mod;}
void dec(ll &a,ll b) {a=(a-b+mod)%mod;}
int prod(ll a,ll b) {return ll(a)*ll(b)%mod;}
int lowbit(ll x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const ll maxn=333333;
ll a[maxn],b[maxn];
ll n,m;

ll dv(ll x,ll y){
	return (x+y-1)/y;
}
bool check(ll mid){//returns if the minimum can be met
	ll cnt=0;
	rep(i,1,n+1){
		ll curr=mid;
		if(a[i]>b[i]){
			curr-=min(dv(mid,a[i]),m)*a[i];
			cnt+=min(dv(mid,a[i]),m);
		}
		if(curr>0){
			cnt+=dv(curr,b[i]);
		}
	}
	return cnt<=m*n;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	rep(i,1,n+1)cin>>a[i];
	rep(i,1,n+1)cin>>b[i];
	
	ll lo=1,hi=1e18;
	while(lo<hi){
		ll mid=(lo+hi+1)>>1;
		if(check(mid))lo=mid;
		else hi=mid-1;
	}
	
	cout<<lo<<endl;
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 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 0 ms 2396 KB Output is correct
9 Correct 1 ms 2440 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 180 ms 5204 KB Output is correct
12 Correct 184 ms 5408 KB Output is correct
13 Correct 130 ms 5212 KB Output is correct
14 Incorrect 424 ms 5332 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 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 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 1 ms 2396 KB Output is correct
9 Correct 72 ms 4720 KB Output is correct
10 Correct 48 ms 4696 KB Output is correct
11 Correct 36 ms 4700 KB Output is correct
12 Correct 29 ms 4744 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Incorrect 5 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 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 0 ms 2396 KB Output is correct
9 Correct 1 ms 2440 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 180 ms 5204 KB Output is correct
12 Correct 184 ms 5408 KB Output is correct
13 Correct 130 ms 5212 KB Output is correct
14 Incorrect 424 ms 5332 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 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 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 1 ms 2396 KB Output is correct
9 Correct 72 ms 4720 KB Output is correct
10 Correct 48 ms 4696 KB Output is correct
11 Correct 36 ms 4700 KB Output is correct
12 Correct 29 ms 4744 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Incorrect 5 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 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 0 ms 2396 KB Output is correct
9 Correct 1 ms 2440 KB Output is correct
10 Correct 3 ms 2396 KB Output is correct
11 Correct 180 ms 5204 KB Output is correct
12 Correct 184 ms 5408 KB Output is correct
13 Correct 130 ms 5212 KB Output is correct
14 Incorrect 424 ms 5332 KB Output isn't correct
15 Halted 0 ms 0 KB -