General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
173399106 Practice:
iftekhar
1734D - 98 C++17 (GCC 9-64) Wrong answer on test 10 46 ms 1576 KB 2022-09-25 10:50:55 2022-09-25 10:50:55
→ Source
/*
                بِسْمِ ٱللَّٰهِ ٱلرَّحْمَٰنِ ٱلرَّحِيمِ                
                Iftekhar Md. Shishir
                Dept. of Information and Communication Engineering
                University of Rajshahi
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll  long long
#define ld  long double
#define printSet(a)  for(auto Data:a) cout<<Data<<" ";cout<<"\n";
#define printVector(a)  for(auto Data:a)cout<<Data<<" ";cout<<"\n";
#define printQueue(Q)  while(!Q.empty())cout<< Q.front()<<" ",Q.pop(); cout<<"\n";

#define all(a)  a.begin(),a.end()
#define rall(a)  a.rbegin(),a.rend()
#define stringToInt(a,x)   stringstream demo(a); demo >> x;
#define intToSting(x,s)   stringstream demu; demu << x; a = demu.str();

#define TxtIO   freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define FastIO   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
#define LCM(a,b)  (a*b)/__gcd(a, b)
#define TestCase   ll t;cin>>t;while(t--)
#define points(x)   fixed<<setprecision(x)
#define pr(x)  cerr << #x << " = " << x << endl;
#define nl  cout<<"\n";
const ld PI= 3.14159265358979323846264338327950288;

using namespace std;
using namespace __gnu_pbds;
template<class T> using indexed_set = tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const long long MOD = 1e9+7 , N = 2e5+10 , INF = INT_FAST64_MAX;

//          U   R  D  L
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
inline ll vin() {ll x;cin >> x;return x;}
ll POW(ll a, ll b) {ll res = 1;while(b){if(b%2)res=(res*a)%MOD;a = (a*a)%MOD; b/=2;}return res;}
vector<ll> DIGITS(ll n){vector<ll>a;while(n)a.push_back(n%10),n/=10;return a;}


string solve()
{
        ll n = vin() , k = vin();
        vector<ll> a(n+1), b;
        for(int i=0; i<n; i++) a[i] = vin();

        if(a[k-1]<0) return "NO";
        if(k == n || k == 1) return "YES";

        // Construct B
        ll curr = 0 , ck = 0 , idx = -1;
        if(a[0]<0) ck = 1;
        for(int i=0; i<n; i++) {
            if((a[i]<0 && !ck) || (a[i]>=0 && ck)) {
                b.push_back(curr);
                curr = 0;
                ck ^= 1;
            }
            curr += a[i];
            if(idx == -1 && i>=k-1) idx = (int)(b.size());
        }
        b.push_back(curr);
        if(idx == -1) idx = (int)(b.size())-1;

        // TRY TO SCAPE THROUGH 0
        int health = b[idx] , sz = b.size(), ii = idx-1 , jj = idx+1;
        while(ii>=0 && jj<= sz-1) 
        {
            if(-b[jj] > health && -b[ii] > health) break;

            if(-b[jj] <= health && sz != jj+1 && b[jj+1]-((-1)*b[jj]) >= 0) {
                health += b[jj] + b[jj+1];
                jj += 2;
                continue;
            }
            if(-b[ii] <= health) {
                if(ii-1 >= 0) {
                    health += b[ii] + b[ii-1];
                    ii-=2;
                }
                else return "YES";
            }
            else {
                if(-b[jj] <= health && sz != jj+1) {
                    health += b[jj] + b[jj+1];
                    jj += 2;
                }
                else if(-b[jj] <= health && sz == jj+1) return "YES";
                else break;
            }
        }
        if(ii<0 || jj>sz-1) return "YES";

        // TRY TO SCAPE THROUGH N
        health = b[idx] , sz = b.size(), ii = idx-1 , jj = idx+1;
        while(ii>=0 && jj<= sz-1) 
        {
            if(-b[jj] > health && -b[ii] > health) break;

            if(-b[ii] <= health && ii-1>=0 && b[ii-1]-((-1)*b[ii]) >= 0) {
                health += b[ii] + b[ii-1];
                ii -= 2;
                continue;
            }
            if(-b[jj] <= health) {
                if(jj+1 < sz) {
                    health += b[jj] + b[jj+1];
                    jj+=2;
                }
                else return "YES";
            }
            else {
                if(-b[ii] <= health && ii-1 >= 0) {
                    health += b[ii] + b[ii-1];
                    ii -= 2;
                }
                else if(-b[ii] <= health && ii-1 < 0) return "YES";
                else break;
            }
        }
        if(ii<0 || jj>sz-1) return "YES";
        return "NO";
}
int main() 
{
        FastIO;
        TestCase {
            cout << solve() << "\n";
            //solve();
        }
        return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details