Submission #886946

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
886946	2023-12-13T08:35:35 Z	stefanneagu	Self Study (JOI22_ho_t2)	C++17	0 / 100	426 ms	11088 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;
    if(a[i] <= b[i]) {
      // cout << "e mai mare b-ul, deci folosim ";
      int cntn = 0;
      cnt += nrm / b[i];
      cntn += nrm / b[i];
      if(nrm % b[i] != 0) {
        cnt ++;
        cntn ++;
      }
      // cout << cntn << endl << endl;
    } else {
      // cout << "e mai mare a-ul, deci folosim ";
      int nrai = nrm / a[i];
      if(nrm % a[i] != 0) {
        nrai ++;
      }
      // 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 << cntn << endl << 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];
  }
  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	2396 KB	Output is correct
2	Correct	1 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	1 ms	2396 KB	Output is correct
6	Correct	1 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	1 ms	2396 KB	Output is correct
10	Correct	3 ms	2392 KB	Output is correct
11	Correct	175 ms	10836 KB	Output is correct
12	Correct	179 ms	11088 KB	Output is correct
13	Correct	131 ms	8948 KB	Output is correct
14	Incorrect	426 ms	8956 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	2392 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2548 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2512 KB	Output is correct
9	Correct	71 ms	7624 KB	Output is correct
10	Correct	48 ms	6492 KB	Output is correct
11	Correct	36 ms	5980 KB	Output is correct
12	Correct	30 ms	5724 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	2 ms	2508 KB	Output is correct
15	Correct	1 ms	2508 KB	Output is correct
16	Correct	1 ms	2392 KB	Output is correct
17	Correct	1 ms	2392 KB	Output is correct
18	Incorrect	5 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	2396 KB	Output is correct
2	Correct	1 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	1 ms	2396 KB	Output is correct
6	Correct	1 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	1 ms	2396 KB	Output is correct
10	Correct	3 ms	2392 KB	Output is correct
11	Correct	175 ms	10836 KB	Output is correct
12	Correct	179 ms	11088 KB	Output is correct
13	Correct	131 ms	8948 KB	Output is correct
14	Incorrect	426 ms	8956 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	2392 KB	Output is correct
3	Correct	1 ms	2392 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2548 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2512 KB	Output is correct
9	Correct	71 ms	7624 KB	Output is correct
10	Correct	48 ms	6492 KB	Output is correct
11	Correct	36 ms	5980 KB	Output is correct
12	Correct	30 ms	5724 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	2 ms	2508 KB	Output is correct
15	Correct	1 ms	2508 KB	Output is correct
16	Correct	1 ms	2392 KB	Output is correct
17	Correct	1 ms	2392 KB	Output is correct
18	Incorrect	5 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	2396 KB	Output is correct
2	Correct	1 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	1 ms	2396 KB	Output is correct
6	Correct	1 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	1 ms	2396 KB	Output is correct
10	Correct	3 ms	2392 KB	Output is correct
11	Correct	175 ms	10836 KB	Output is correct
12	Correct	179 ms	11088 KB	Output is correct
13	Correct	131 ms	8948 KB	Output is correct
14	Incorrect	426 ms	8956 KB	Output isn't correct
15	Halted	0 ms	0 KB	-