Alex_tz307

pitici infopro C1

Nov 15th, 2020
321
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5.  
  6. ifstream fin("pitici.in");
  7. ofstream fout("pitici.out");
  8.  
  9. int32_t main() {
  10.     fin.sync_with_stdio(false);
  11.     fout.sync_with_stdio(false);
  12.     fin.tie(nullptr);
  13.     fout.tie(nullptr);
  14.     int N;
  15.     fin >> N;
  16.     vector < int > a(N + 2), b(N + 2);
  17.     for(int i = 1; i <= N; ++i) {
  18.         fin >> a[i];
  19.         a[i] += a[i - 1];
  20.     }
  21.     for(int i = 1; i <= N; ++i)
  22.         fin >> b[i];
  23.     vector < int > v(N + 2);
  24.     for(int i = 1; i <= N; ++i) {
  25.         ++v[i];
  26.         int st = i, dr = N, ans = N;
  27.         while(st <= dr) {
  28.             int mid = (st + dr) >> 1;
  29.             int sum = a[mid] - a[i - 1];
  30.             if(sum >= b[i]) {
  31.                 ans = mid;
  32.                 dr = mid - 1;
  33.             }
  34.             else
  35.                 st = mid + 1;
  36.         }
  37.         --v[ans + 1];
  38.     }
  39.     int mx = 0, cnt = 0;
  40.     for(int i = 1; i <= N; ++i) {
  41.         v[i] += v[i - 1];
  42.         if(v[i] > mx) {
  43.             mx = v[i];
  44.             cnt = 1;
  45.         }
  46.         else
  47.             if(v[i] == mx)
  48.                 ++cnt;
  49.     }
  50.     fout << mx << ' ' << cnt;
  51. }
  52.  
Advertisement
Add Comment
Please, Sign In to add comment