Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void solve()
- {
- ll N, K;
- cin >> N >> K;
- vector<ll> B(N);
- for (ll i = 0; i < N; i++)
- {
- cin >> B[i];
- }
- ll mn = N + 1;
- vector<ll> pre = B;
- for (ll i = 1; i < N; i++)
- {
- pre[i] += pre[i - 1];
- }
- vector<ll> preSum(1e6 + 5, -1);
- for (ll l = 0; l < N; l++)
- {
- for (ll x = l - 2; x >= 0; x--)
- {
- ll sum = pre[l - 2];
- if (x != 0)
- {
- sum -= pre[x - 1];
- }
- if (sum < K)
- {
- if (preSum[sum] == -1)
- {
- preSum[sum] = (l - 2 - x + 1);
- }
- else
- {
- preSum[sum] = min(preSum[sum], l - 2 - x + 1);
- }
- }
- else
- {
- break;
- }
- }
- for (ll r = l; r < N; r++)
- {
- ll sum = pre[r];
- if (l != 0)
- {
- sum -= pre[l - 1];
- }
- if (sum > K)
- {
- break;
- }
- else if (sum == K)
- {
- mn = min(mn, r - l + 1);
- break;
- }
- else
- {
- if (preSum[K - sum] != -1)
- {
- mn = min(mn, preSum[K - sum] + (r - l + 1));
- }
- }
- }
- }
- cout << "Case #" << cas << ": " << (mn == N + 1 ? -1 : mn) << endl;
- return;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement