fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5 + 5;
  6.  
  7. int r[N];
  8. int e[N];
  9. int need[N];
  10. int n, m;
  11.  
  12. bool can(int x) {
  13.   memset(r, -1, sizeof r);
  14.   for(int i = 1; i <= x; i++) {
  15.     if(e[i] == 0) continue;
  16.     r[e[i]] = i;
  17.   }
  18.   for(int i = 1; i <= m; i++) {
  19.     if(r[i] == -1) return false;
  20.   }
  21.   int days = 0;
  22.   for(int i = 1; i <= x; i++) {
  23.     if(e[i] == 0) days++;
  24.     else if(r[e[i]] == i) {
  25.       if(days >= need[e[i]]) {
  26.         days -= need[e[i]];
  27.       }
  28.       else {
  29.         return false;
  30.       }
  31.     }
  32.     else days++;
  33.   }
  34.   return true;
  35. }
  36.  
  37. int main() {
  38.   cin >> n >> m;
  39.   for(int i = 1; i <= n; i++) {
  40.     cin >> e[i];
  41.   }
  42.   for(int i = 1; i <= m; i++) {
  43.     cin >> need[i];
  44.   }
  45.   int l = 1, r = n;
  46.   int best = -1;
  47.   while(l <= r) {
  48.     int mid = (l + r) / 2;
  49.     if(can(mid)) {
  50.       best = mid, r = mid - 1;
  51.     }
  52.     else {
  53.       l = mid + 1;
  54.     }
  55.   }
  56.   cout << best;
  57. }
Success #stdin #stdout 0s 16408KB
comments (?)
stdin
copy 
5 1
1 1 1 1 1
5
stdout
copy 
-1
https://ideone.com/9b25GY
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!