oj.uz

Submission #1110759

# Submission time Handle Problem Language Result Execution time Memory
1110759 2024-11-10T11:36:03 Z Flandre Self Study (JOI22_ho_t2) C++17
0 / 100
 101 ms 10904 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;

// loal is the cutest girl

#define ll long long
#define int ll
#define ld long double
#define pow2(x) (x)*(x)
#define le left
#define ri right
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define pll pair<long long, long long>
#define isvowel(x) (x) == 'a' || (x) == 'i' || (x) == 'u' || (x) == 'e' || (x) == 'o'
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

const ld EPS = 1e-9;
const ld PI = 3.141592653589793238462643383279502884197169399375105820974944;

const int maxn = 3e5+5;
int n, m;
int a[maxn];
int b[maxn];

bool solve(ll amo) {
  ll needed = 0;
  for (int i = 0; i < n; i++) {
    int now = a[i]*m;
    if (now < amo) {
      needed += (amo-now+b[i]-1)/b[i];
    } else {
      needed -= m-(amo+a[i]-1)/a[i];
    }
  }
  return needed <= 0;
}

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    a[i] = max(a[i], b[i]);
  }

  ll l = 1, r = 1e18;

  while (l < r) {
    ll mid = (l+r+1)/2;
    if (solve(mid)) l = mid;
    else r = mid-1;
  }

  cout << l << '\n';

  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2552 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 3 ms 2640 KB Output is correct
11 Correct 93 ms 10828 KB Output is correct
12 Correct 98 ms 10904 KB Output is correct
13 Correct 73 ms 8776 KB Output is correct
14 Incorrect 101 ms 8768 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 2384 KB Output is correct
2 Correct 1 ms 2600 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 44 ms 7504 KB Output is correct
10 Correct 36 ms 6480 KB Output is correct
11 Correct 23 ms 5968 KB Output is correct
12 Correct 19 ms 5712 KB Output is correct
13 Correct 1 ms 2536 KB Output is correct
14 Correct 1 ms 2384 KB Output is correct
15 Correct 1 ms 2384 KB Output is correct
16 Correct 1 ms 2640 KB Output is correct
17 Correct 1 ms 2384 KB Output is correct
18 Incorrect 2 ms 2384 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 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2552 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 3 ms 2640 KB Output is correct
11 Correct 93 ms 10828 KB Output is correct
12 Correct 98 ms 10904 KB Output is correct
13 Correct 73 ms 8776 KB Output is correct
14 Incorrect 101 ms 8768 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 2384 KB Output is correct
2 Correct 1 ms 2600 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 44 ms 7504 KB Output is correct
10 Correct 36 ms 6480 KB Output is correct
11 Correct 23 ms 5968 KB Output is correct
12 Correct 19 ms 5712 KB Output is correct
13 Correct 1 ms 2536 KB Output is correct
14 Correct 1 ms 2384 KB Output is correct
15 Correct 1 ms 2384 KB Output is correct
16 Correct 1 ms 2640 KB Output is correct
17 Correct 1 ms 2384 KB Output is correct
18 Incorrect 2 ms 2384 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 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2552 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 3 ms 2640 KB Output is correct
11 Correct 93 ms 10828 KB Output is correct
12 Correct 98 ms 10904 KB Output is correct
13 Correct 73 ms 8776 KB Output is correct
14 Incorrect 101 ms 8768 KB Output isn't correct
15 Halted 0 ms 0 KB -