Subtask ~1~

• Chọn tất cả các cặp ~L, R~.
• Với mỗi cặp, ta duyệt từ ~L~ đến ~R~ để tính tổng và cập nhật kết quả.
• Đpt: ~O(n^3)~.

Subtask ~2~

• Với mỗi ~L~, ta vừa chọn ~R~ vừa tính tổng để giảm độ phức tạp.
• Đpt: ~O(n^2)~

  Code tham khảo

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;

int n, a[N];
long long S;

int main() {
    freopen("CAU3.INP", "r", stdin);
    freopen("CAU3.OUT", "w", stdout);
    cin >> n >> S;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 100000000;
    for (int l = 1; l <= n; l++) {
        long long tmp = 0;
        for (int r = l; r <= n; r++) {
            tmp += a[r];
            if (tmp >= S) ans = min(ans, r - l + 1);
        }
    }
    cout << (ans == 100000000 ? -1 : ans);
    return 0;
}

Subtask ~3, 4~

• Ta có thể áp dụng kỹ thuật 2 con trỏ để duyệt qua mảng tối đa ~2~ lần.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 5;

int n, a[N];
long long S;

int main() {
    freopen("CAU3.INP", "r", stdin);
    freopen("CAU3.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> S;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 100000000;
    long long sum = 0;
    for (int l = 1, r = 1; r <= n; r++) {
        sum += a[r];
        while (sum >= S) {
            sum -= a[l];
            ans = min(ans, r - l + 1);
            l++;
        }
    }
    cout << (ans == 100000000 ? -1 : ans);
    return 0;
}