1890D - Doremy's Connecting Plan - CodeForces Solution

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue> 
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <ctime>
#include <assert.h>
#include <deque>
#define SEQ 19
 
using namespace std;
 
typedef pair<long long , long long> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> piii;
typedef pair<int, long long > pil;
typedef long long ll;
typedef unsigned long long ull;
const int N = 400086, MOD = 998244353, INF = 0x3f3f3f3f, MID = 333, M = 1000086;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2}, dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int n, m, cnt;
vector<int> num;
ll res, w[N];

int read() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {  
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}

int lowbit(int x)
{
    return x & -x;
}
 
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
 
inline double rand(double l, double r)
{
    return (double)rand() / RAND_MAX * (r - l) + l;
}
 
inline ll qmi(ll a, ll b, ll c)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res = res * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return res;
}
 
inline ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
 
inline ll C(ll a, ll b)
{
    if (a < b) return 0;
    ll res = 1;
    for (int i = 1, j = a; i <= b; i++, j--)
    {
        res = res * j % MOD;
        res = res * qmi(i, MOD - 2, MOD) % MOD;
    }
    return res;
}
 
inline int find(int x)
{
    return lower_bound(num.begin(), num.end(), x) - num.begin();
}


ll s[N];
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        ll sum = 0;
        cin >> n >> m;
        for (int i = 1; i < n + 1; i++) scanf("%lld", w + i), s[i] = s[i - 1] + w[i];
        int r = 0;
        for (int i = n; i > 1; i--)
            if (w[1] + w[i] >= (ll)m * i)
            {
                r = i;
                break;
            }
        if (!r) { printf("No\n"); continue; }
        sum = s[r];
        for (int i = r + 1; i < n + 1; i++)
            if (s[r] + w[i] >= (ll)i * m)
                sum += s[i] - s[r], r = i;
        if (r == n) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}