Submission #1077729

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1077729	2024-08-27T08:45:10 Z	Acanikolic	Self Study (JOI22_ho_t2)	C++14	0 / 100	150 ms	7516 KB

Main

#include <bits/stdc++.h>  

#define int long long 

#define pb push_back
 
#define F first
 
#define S second
 
using namespace std;
 
const int N = 1e5 + 10;
 
const int mod = 1e9 + 7;
 
const int inf = 1e9;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 	
 	int n,m;
 	cin >> n >> m;
 	vector<int>a(n + 1),b(n + 1),c(n + 1);
 	for(int i = 1; i <= n; i++) cin >> a[i];
 	for(int i = 1; i <= n; i++) cin >> b[i];
 	for(int i = 1; i <= n; i++) c[i] = max(a[i],b[i]);
 	int l = 1,r = 1e18,ans = 0;
 	while(l <= r) {
 		int mid = (l + r) / 2,rest = 0;
 		for(int i = 1; i <= n; i++) {
 			if(b[i] >= a[i]) {
 				int need = (mid + b[i] - 1) / b[i];
 				rest += m - need;
 				continue;
 			}
 			int c = min(m,(mid + a[i] - 1) / a[i]);
 			int k = mid - a[i] * c;
 			if(k < 0) rest += m - c;
 		}
 		for(int i = 1; i <= n; i++) {
 			if(b[i] >= a[i]) {
 				continue;
 			}
 			int c = min(m,(mid + a[i] - 1) / a[i]);
 			int k = mid - a[i] * c;
 			if(k > 0) {
 				rest -= (k + b[i] - 1) / b[i];
 				if(rest < 0) break;
 			}
 		}
		if(rest >= 0) {
			ans = mid;
			l = mid + 1;
		}else {
			r = mid - 1;
		}
 	}
 	cout << ans;
    return 0;
}

Subtask #1

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 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	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	2 ms	344 KB	Output is correct
11	Correct	150 ms	7260 KB	Output is correct
12	Correct	138 ms	7484 KB	Output is correct
13	Correct	93 ms	7260 KB	Output is correct
14	Correct	94 ms	7516 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Incorrect	98 ms	7260 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Incorrect	98 ms	7260 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 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	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	2 ms	344 KB	Output is correct
11	Correct	150 ms	7260 KB	Output is correct
12	Correct	138 ms	7484 KB	Output is correct
13	Correct	93 ms	7260 KB	Output is correct
14	Correct	94 ms	7516 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Incorrect	98 ms	7260 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Incorrect	98 ms	7260 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 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	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	2 ms	344 KB	Output is correct
11	Correct	150 ms	7260 KB	Output is correct
12	Correct	138 ms	7484 KB	Output is correct
13	Correct	93 ms	7260 KB	Output is correct
14	Correct	94 ms	7516 KB	Output is correct
15	Correct	0 ms	344 KB	Output is correct
16	Incorrect	98 ms	7260 KB	Output isn't correct
17	Halted	0 ms	0 KB	-