fork(9) download
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int time(int r, int m, const char *bridge) {
  8. int i = 0, res = 1;
  9. while (i + r <= m) {
  10. res++;
  11. i += r;
  12. while (bridge[i] == '1') i--;
  13. }
  14. return res;
  15. }
  16.  
  17. int main() {
  18. ios::sync_with_stdio(false); cin.tie(0);
  19. int n, m; cin >> n >> m;
  20. vector<int> a(n);
  21. for (auto &x: a) cin >> x;
  22. string bridge; cin >> bridge;
  23. bridge = '0' + bridge + '0';
  24. vector<int> cache(101, 0);
  25. for (auto &x: a) {
  26. if (!cache[x]) x = cache[x] = time(x, m, bridge.data());
  27. else x = cache[x];
  28. }
  29. sort(a.begin(), a.end());
  30. if (n == 1) cout << a[0];
  31. else if (n == 2) cout << a[1];
  32. else {
  33. int f0 = a[0], f1 = a[1];
  34. for (int i=2; i<n; i++) {
  35. int f2 = min(f0 + a[0] + 2*a[1] + a[i], f1 + a[0] + a[i]);
  36. f0 = f1, f1 = f2;
  37. }
  38. cout << f1;
  39. }
  40. return 0;
  41. }
  42.  
Time limit exceeded #stdin #stdout 5s 15408KB
stdin
Standard input is empty
stdout
Standard output is empty