oj.uz

Submission #907577

# Submission time Handle Problem Language Result Execution time Memory
907577 2024-01-15T21:35:38 Z vjudge1 Self Study (JOI22_ho_t2) C++17
64 / 100
 210 ms 16212 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
typedef __int128_t ll;
typedef pair<int, int> pii;
typedef vector<ll> vi;

std::istream& operator>>( std::istream& src, __int128_t& value )
{
	long long v;src>>v;
	value = (ll)v;
	return src;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	ll n,m;cin>>n>>m;
	vi a(n);rep(i,0,n)cin>>a[i];
	vi b(n);rep(i,0,n)cin>>b[i];
	bool eq = true;
	rep(i,0,n)if(a[i]!=b[i]) eq=false;
	ll worst = 2e18;
	if(m==1){
		rep(i,0,n) worst=min(worst,max(a[i],b[i]));
	}else if(eq){
		ll lo = 0;
		ll hi = 2e18;
		while(lo+1<hi){
			ll mid = lo+(hi-lo)/2;
			ll cost = 0;
			rep(i,0,n) cost += (mid+a[i]-1)/a[i];
			if(cost<=n*m) lo=mid;
			else hi=mid;
		}
		worst=lo;
	}else if(n*m <= 300000){
		// priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
		// rep(i,0,n) pq.push({0,i});
		// rep(_,0,n*m){
		// 	auto p = pq.top(); pq.pop();
		// 	pq.push({p.F + a[p.S], p.S});
		// }
		// worst = pq.top().F;
	}
	cout<<(long long)worst<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 380 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 48 ms 9840 KB Output is correct
12 Correct 49 ms 9808 KB Output is correct
13 Correct 41 ms 9836 KB Output is correct
14 Correct 40 ms 9816 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 25 ms 9776 KB Output is correct
17 Correct 49 ms 9816 KB Output is correct
18 Correct 47 ms 9808 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 25 ms 9776 KB Output is correct
3 Correct 49 ms 9816 KB Output is correct
4 Correct 47 ms 9808 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 392 KB Output is correct
13 Correct 75 ms 5140 KB Output is correct
14 Correct 50 ms 3420 KB Output is correct
15 Correct 38 ms 2652 KB Output is correct
16 Correct 30 ms 2140 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 3 ms 604 KB Output is correct
23 Correct 3 ms 608 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 380 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 48 ms 9840 KB Output is correct
12 Correct 49 ms 9808 KB Output is correct
13 Correct 41 ms 9836 KB Output is correct
14 Correct 40 ms 9816 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 592 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 392 KB Output is correct
23 Correct 75 ms 5140 KB Output is correct
24 Correct 50 ms 3420 KB Output is correct
25 Correct 38 ms 2652 KB Output is correct
26 Correct 30 ms 2140 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 3 ms 604 KB Output is correct
33 Correct 3 ms 608 KB Output is correct
34 Correct 1 ms 600 KB Output is correct
35 Correct 25 ms 9776 KB Output is correct
36 Correct 49 ms 9816 KB Output is correct
37 Correct 47 ms 9808 KB Output is correct
38 Incorrect 0 ms 348 KB Output isn't correct
39 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 392 KB Output is correct
9 Correct 75 ms 5140 KB Output is correct
10 Correct 50 ms 3420 KB Output is correct
11 Correct 38 ms 2652 KB Output is correct
12 Correct 30 ms 2140 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 3 ms 608 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 25 ms 9776 KB Output is correct
22 Correct 49 ms 9816 KB Output is correct
23 Correct 47 ms 9808 KB Output is correct
24 Correct 30 ms 1892 KB Output is correct
25 Correct 80 ms 7260 KB Output is correct
26 Correct 17 ms 1880 KB Output is correct
27 Correct 150 ms 15904 KB Output is correct
28 Correct 150 ms 15508 KB Output is correct
29 Correct 151 ms 15764 KB Output is correct
30 Correct 161 ms 15444 KB Output is correct
31 Correct 202 ms 15700 KB Output is correct
32 Correct 208 ms 11004 KB Output is correct
33 Correct 210 ms 16212 KB Output is correct
34 Correct 204 ms 11012 KB Output is correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 380 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 48 ms 9840 KB Output is correct
12 Correct 49 ms 9808 KB Output is correct
13 Correct 41 ms 9836 KB Output is correct
14 Correct 40 ms 9816 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 592 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 392 KB Output is correct
23 Correct 75 ms 5140 KB Output is correct
24 Correct 50 ms 3420 KB Output is correct
25 Correct 38 ms 2652 KB Output is correct
26 Correct 30 ms 2140 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 3 ms 604 KB Output is correct
33 Correct 3 ms 608 KB Output is correct
34 Incorrect 0 ms 348 KB Output isn't correct
35 Halted 0 ms 0 KB -