Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <bitset>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <map>
- #include <unordered_set>
- #include <math.h>
- #include <iomanip>
- typedef long long ll;
- using namespace std;
- #define all(v) v.begin(), v.end()
- #define pb push_back
- #define ff first
- #define ss second
- #define fori(n) for (int i = 0; i < n; i++)
- #define forj(n) for (int j = 0; j < n; j++)
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
- #pragma GCC optimize("fast-math")
- #pragma GCC optimize "-O3"
- /*
- int main() {
- int n, a, b;
- cin >> n >> a >> b;
- string s;
- cin >> s;
- int cnt0 = 0, cnt1 = 0, cnt2 = 0;
- fori(s.size()) s[i] -= '0';
- fori(s.size()) {
- if (s[i] == 0) cnt0++;
- else if (s[i] == 1) cnt1++;
- else cnt2++;
- }
- }
- */
- int main() {
- int n, k;
- cin >> n >> k;
- vector < int > a(n);
- fori(n) cin >> a[i];
- int la = 0, ra = 1e9; /// максимальная длина(нам же ещё надо минимизировать)
- int sum = 0;
- int r = -1;
- for (int l = 0; l < n; l++) {
- /// так как у тебя до этого было l был l - 1, то ты должен убрать a[l - 1]
- if (l) sum -= a[l - 1]; /// если у тебя был такой элемент вообще, то ты его убираешь
- if (r < l) {
- r++;
- sum += a[r];
- }
- while (true) {
- if (r == n - 1) break; /// если дальше уже нет элементов, которые можно взять, то мы сосем бибу
- if (sum < k) {
- /// если у тебя ещё не набрана нужная сумма, то мы её набираем(справедливо)
- r++;
- sum += a[r];
- } else break;
- /// иначе sum >= k и тебе не надо идти дальше
- }
- if (sum == k) {
- if (r - l < ra - la) {
- ra = r;
- la = l;
- }
- }
- }
- if (la == 0 && ra == 1e9) {
- /// если наша длина ни разу не минимизировалась, то она осталась прежней
- /// и мы ничего ни разу не нашли
- cout << -1;
- return 0;
- }
- cout << la + 1 << " " << ra + 1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement