rembocoder

Untitled

May 4th, 2023
686
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. #define int long long
  8.  
  9. signed main() {
  10.     int n, m;
  11.     cin >> n >> m;
  12.     vector<int> day(n), k(m + 2);
  13.     for (int i = 0; i < n; ++i) {
  14.         cin >> day[i];
  15.         day[i]--;
  16.     }
  17.     for (int i = 1; i <= m; ++i) {
  18.         cin >> k[i];
  19.     }
  20.     int l = -1, r = n;
  21.     while (r - l > 1) {
  22.         vector<pair<int, int>> loc;
  23.         vector<bool> used(m, 0);
  24.         int mid = (r + l) / 2;
  25.         for (int i = mid; i >= 0; --i) {
  26.             if (data[i] != -1 && !used[day[i]]) {
  27.                 used[day[i]] = true;
  28.                 loc.emplace_back(day[i], i);
  29.             }
  30.         }
  31.         reverse(loc.begin(), loc.end());
  32.         if (loc.size() < m) {
  33.             l = mid;
  34.         }
  35.         int busy = 0;
  36.         bool good = true;
  37.         for (int i = 0; i < loc.size(); ++i) {
  38.             int have = loc[i].second - busy;
  39.             if (have >= k[loc[i].first]) {
  40.                 busy += k[loc[i].first] + 1;
  41.             } else {
  42.                 good = false;
  43.                 break;
  44.             }
  45.         }
  46.         if (!good) {
  47.             l = mid;
  48.         } else {
  49.             r = mid;
  50.         }
  51.     }
  52.     if (r == n) {
  53.         cout << -1;
  54.         return 0;
  55.     }
  56.     cout << r + 1;
  57.     return 0;
  58. }
  59.  
Advertisement
Add Comment
Please, Sign In to add comment