Submission #886967

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
886967	2023-12-13T09:39:54 Z	stefanneagu	Self Study (JOI22_ho_t2)	C++17	0 / 100	436 ms	8276 KB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int nmax = 3e5 + 1;

int a[nmax], b[nmax], n, m;

bool check(int nrm) {
  int cnt = 0;
  for(int i = 1; i <= n; i ++) {
    //cout << "Suntem la " << i << endl;
    int nrai = nrm / a[i];
    if(nrm % a[i] != 0) {
      nrai ++;
      //cout << "uWu(" << a[i] << " " << nrm << ") ";
    }
    // cout << " nrai = " << nrai << " si al final ";
    int cntn = 0;
    if(nrai <= m) {
      cnt += nrai;
      cntn += nrai;
    } else {
      nrai = m;
      int rm = nrm - a[i] * nrai;
      cnt += rm / b[i];
      cnt += nrai;
      cntn += rm / b[i];
      cntn += nrai;
      if(rm % b[i] != 0) {
        cnt ++;
        cntn ++;
      }
    }
    //cout << "Cnt: " << cntn << endl;
  }
  // cout << "Cnt final: " << cnt << endl;
  return (cnt <= n * m);
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  for(int i = 1; i <= n; i ++) {
    cin >> a[i];
  }
  for(int i = 1; i <= n; i ++) {
    cin >> b[i];
    a[i] = max(a[i], b[i]);
  }
  int l = 0, r = 1e18, ans = 0;
  while(l <= r) {
    int mid = (l + r) / 2;
    if(check(mid) == true) {
      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	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2392 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	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	4 ms	2396 KB	Output is correct
11	Correct	202 ms	8276 KB	Output is correct
12	Correct	199 ms	8016 KB	Output is correct
13	Correct	206 ms	7000 KB	Output is correct
14	Incorrect	436 ms	7184 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	2396 KB	Output is correct
2	Correct	1 ms	2512 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	0 ms	2516 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	106 ms	6460 KB	Output is correct
10	Correct	70 ms	6164 KB	Output is correct
11	Correct	51 ms	5720 KB	Output is correct
12	Correct	43 ms	5492 KB	Output is correct
13	Correct	1 ms	2392 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	0 ms	2396 KB	Output is correct
18	Incorrect	8 ms	2392 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	2392 KB	Output is correct
2	Correct	1 ms	2392 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	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	4 ms	2396 KB	Output is correct
11	Correct	202 ms	8276 KB	Output is correct
12	Correct	199 ms	8016 KB	Output is correct
13	Correct	206 ms	7000 KB	Output is correct
14	Incorrect	436 ms	7184 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	2396 KB	Output is correct
2	Correct	1 ms	2512 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	0 ms	2516 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	106 ms	6460 KB	Output is correct
10	Correct	70 ms	6164 KB	Output is correct
11	Correct	51 ms	5720 KB	Output is correct
12	Correct	43 ms	5492 KB	Output is correct
13	Correct	1 ms	2392 KB	Output is correct
14	Correct	1 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	0 ms	2396 KB	Output is correct
18	Incorrect	8 ms	2392 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	2392 KB	Output is correct
2	Correct	1 ms	2392 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	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2392 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	4 ms	2396 KB	Output is correct
11	Correct	202 ms	8276 KB	Output is correct
12	Correct	199 ms	8016 KB	Output is correct
13	Correct	206 ms	7000 KB	Output is correct
14	Incorrect	436 ms	7184 KB	Output isn't correct
15	Halted	0 ms	0 KB	-