Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2019
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.54 KB | None | 0 0
  1. #include <iostream>
  2. #include <bitset>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <unordered_set>
  8. #include <math.h>
  9. #include <iomanip>
  10. typedef long long ll;
  11. using namespace std;
  12. #define all(v) v.begin(), v.end()
  13. #define pb push_back
  14. #define ff first
  15. #define ss second
  16. #define fori(n) for (int i = 0; i < n; i++)
  17. #define forj(n) for (int j = 0; j < n; j++)
  18.  
  19. #pragma GCC optimize("unroll-loops")
  20. #pragma GCC optimize("Ofast")
  21. #pragma GCC optimize("no-stack-protector")
  22. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  23. #pragma GCC optimize("fast-math")
  24. #pragma GCC optimize "-O3"
  25.  
  26.  
  27. /*
  28. int main() {
  29. int n, a, b;
  30. cin >> n >> a >> b;
  31. string s;
  32. cin >> s;
  33. int cnt0 = 0, cnt1 = 0, cnt2 = 0;
  34. fori(s.size()) s[i] -= '0';
  35. fori(s.size()) {
  36. if (s[i] == 0) cnt0++;
  37. else if (s[i] == 1) cnt1++;
  38. else cnt2++;
  39. }
  40.  
  41. }
  42. */
  43.  
  44. int main() {
  45. int n, k;
  46. cin >> n >> k;
  47. vector < int > a(n);
  48. fori(n) cin >> a[i];
  49. int la = 0, ra = 1e9; /// максимальная длина(нам же ещё надо минимизировать)
  50. int sum = 0;
  51. int r = -1;
  52. for (int l = 0; l < n; l++) {
  53. /// так как у тебя до этого было l был l - 1, то ты должен убрать a[l - 1]
  54. if (l) sum -= a[l - 1]; /// если у тебя был такой элемент вообще, то ты его убираешь
  55. if (r < l) {
  56. r++;
  57. sum += a[r];
  58. }
  59. while (true) {
  60. if (r == n - 1) break; /// если дальше уже нет элементов, которые можно взять, то мы сосем бибу
  61. if (sum < k) {
  62. /// если у тебя ещё не набрана нужная сумма, то мы её набираем(справедливо)
  63. r++;
  64. sum += a[r];
  65. } else break;
  66. /// иначе sum >= k и тебе не надо идти дальше
  67. }
  68. if (sum == k) {
  69. if (r - l < ra - la) {
  70. ra = r;
  71. la = l;
  72. }
  73. }
  74. }
  75. if (la == 0 && ra == 1e9) {
  76. /// если наша длина ни разу не минимизировалась, то она осталась прежней
  77. /// и мы ничего ни разу не нашли
  78. cout << -1;
  79. return 0;
  80. }
  81. cout << la + 1 << " " << ra + 1;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement