1734D - Slime Escape - CodeForces Solution


data structures dp greedy two pointers *1800

Please click on ads to support us..

Python Code:

for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    r = k
    k -= 1
    l = k - 1
    x = y = 0
    mr = ml = 0
    while l >= 0 and r < n:
        if l >= 0  and (a[k] + a[l] + x + mr >= 0):
            x += a[l]
            ml = max(x, ml)
            l -= 1
        elif r < n and (a[k] + a[r] + y + ml >= 0):
            y += a[r]
            mr = max(y, mr)
            r += 1
        else:
            break
 
    if l == -1 or r == n:
        print("YES")
    else:
        print("NO")

C++ Code:

// Hi
#include <bits/stdc++.h>
#define f(i, n) for (int i = 0; i < n; i++)
#define f1(i, n) for (int i = 1; i <= n; i++)
#define fn(i, j, k) for (int i = j; i <= k; i++)
#define maan  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long int
#define MOD 1000000007

using namespace std;

// void maan() 
// {
//   
//   #ifndef ONLINE_JUDGE
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);
//   #endif 
// }

void solve()
{
  ll p,q;cin>>p>>q;
  ll b[p];
  f(i,p) cin>>b[i];
  vector<ll>v(p+1,0);
  f(i,p) v[i+1]=b[i]+v[i];
  ll i=q-1,j=q,c1=v[q-1],c2=v[q];
  while (i>0 && j<p)
  {
    if (c1<=v[j+1]) c2=max(c2,v[j+1]),j+=1;
    else if (c2>=v[i-1]) c1=min(c1,v[i-1]),i-=1;
    else break;
  }
  if (i>0 && j<p) cout<<"NO\n";
  else cout<<"YES\n";

  return;
}

int main()
{
  maan
  int r;cin>>r;while (r--)
  {
    solve();
  }

  return 0;
}
/*
6
7 4
-1 -2 -3 6 -2 -3 -1
3 1
232 -500 -700
7 4
-1 -2 -4 6 -2 -4 -1
8 4
-100 10 -7 6 -2 -3 6 -10
8 2
-999 0 -2 3 4 5 6 7
7 3
7 3 3 4 2 1 1

*/


Comments

Submit
0 Comments
More Questions

1701C - Schedule Management
791C - Bear and Different Names
940D - Alena And The Heater
1747B - BAN BAN
1747A - Two Groups
1747C - Swap Game
1183D - Candy Box (easy version)
777B - Game of Credit Cards
1362A - Johnny and Ancient Computer
900C - Remove Extra One
328A - IQ Test
290B - QR code
290A - Mysterious strings
1593E - Gardener and Tree
290D - Orange
1027B - Numbers on the Chessboard
813A - The Contest
1560E - Polycarp and String Transformation
182D - Common Divisors
145A - Lucky Conversion
46B - T-shirts from Sponsor
545E - Paths and Trees
146B - Lucky Mask
1257E - The Contest
932C - Permutation Cycle
1423K - Lonely Numbers
831C - Jury Marks
94B - Friends
443B - Kolya and Tandem Repeat
582B - Once Again