Advertisement
Valkyrie006

Untitled

Oct 16th, 2021
42
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. void solve()
  2. {
  3.     ll N, K;
  4.     cin >> N >> K;
  5.     vector<ll> B(N);
  6.     for (ll i = 0; i < N; i++)
  7.     {
  8.         cin >> B[i];
  9.     }
  10.  
  11.     ll mn = N + 1;
  12.     vector<ll> pre = B;
  13.     for (ll i = 1; i < N; i++)
  14.     {
  15.         pre[i] += pre[i - 1];
  16.     }
  17.     vector<ll> preSum(1e6 + 5, -1);
  18.     for (ll l = 0; l < N; l++)
  19.     {
  20.         for (ll x = l - 2; x >= 0; x--)
  21.         {
  22.             ll sum = pre[l - 2];
  23.             if (x != 0)
  24.             {
  25.                 sum -= pre[x - 1];
  26.             }
  27.             if (sum < K)
  28.             {
  29.                 if (preSum[sum] == -1)
  30.                 {
  31.                     preSum[sum] = (l - 2 - x + 1);
  32.                 }
  33.                 else
  34.                 {
  35.                     preSum[sum] = min(preSum[sum], l - 2 - x + 1);
  36.                 }
  37.             }
  38.             else
  39.             {
  40.                 break;
  41.             }
  42.         }
  43.         for (ll r = l; r < N; r++)
  44.         {
  45.             ll sum = pre[r];
  46.             if (l != 0)
  47.             {
  48.                 sum -= pre[l - 1];
  49.             }
  50.             if (sum > K)
  51.             {
  52.                 break;
  53.             }
  54.             else if (sum == K)
  55.             {
  56.                 mn = min(mn, r - l + 1);
  57.                 break;
  58.             }
  59.             else
  60.             {
  61.                 if (preSum[K - sum] != -1)
  62.                 {
  63.                     mn = min(mn, preSum[K - sum] + (r - l + 1));
  64.                 }
  65.             }
  66.         }
  67.     }
  68.     cout << "Case #" << cas << ": " << (mn == N + 1 ? -1 : mn) << endl;
  69.     return;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement