Идея решения: Попробуем просимулировать процесс. Пусть $$$x = 1, y = 4$$$. Логично начать с $$$y$$$, так как оно больше. Но если просто так ставить подряд, получим:

YYYYX

— а так нельзя, ведь запрещено делать 3 гола подряд. Тогда возможное разбиение:

YYXYY

Теперь проверим, что будет, если увеличить $$$y$$$ ещё на 1. В таком случае корректного разбиения уже не получится. Значит, должно выполняться условие:

Аналогично для второго тайма: там значения считаются как разность, т.е. $$$x = c-a, \; y = d-b$$$.

Таким образом, ответ положительный тогда и только тогда, когда условие верно для обоих таймов.

Алгоритм:

1. Считаем $$$x, y$$$ для первого и второго таймов.
2. Проверяем условие.
3. Если оно выполняется — выводим YES, иначе NO.

#include <iostream>
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define s second
#define f first
using namespace std;
void bruh(){
  double a,b,c,d; cin >> a >> b >> c >> d;
  if(max(a,b)<=(min(a,b)+1)*2 && max(c-a,d-b)<=(min(c-a,d-b)+1)*2){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}

int main() 
{
  ll t; cin >> t;
  while (t--){
    bruh();
  }
}

Идея решения: Условие задачи: для каждого $$$p_i$$$, где $$$s_i = 1$$$, нужно, чтобы он не был максимумом:

• на префиксе $$$[0, i]$$$, если $$$i \geq k$$$;
• на суффиксе $$$[i, n]$$$, если $$$n-i+1 \geq k$$$.

Тогда позиция считается валидной.

Построение: Сначала выведем все позиции единичек в порядке возрастания. Затем — позиции нулей также в порядке возрастания.

Когда решения нет: Если подряд идёт как минимум $$$k$$$ единичек:

s[i] = s[i+1] = ... = s[i+k] = 1

то последняя единичка в таком блоке обязательно станет максимумом на своём префиксе, и условие нарушится.

Итого:

• Если есть подряд $$$k$$$ единичек — ответ NO.
• Иначе — перестановку можно построить описанным алгоритмом.

#include <iostream>
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define s second
#define f first
using namespace std;
void bruh(){
  ll n,k; cin >> n >> k;
  ll cnt = 0;
  string s; cin>>s;
  bool opt = 1;
  map<ll,ll> mp;
  vector<ll> temp1;
  vector<ll> temp2;
  for (ll i = 0;i<n;i++){
    if(s[i]=='1'){
     // cnt++;
      mp[1]++;
      temp1.pb(i);
      if(++cnt>=k){
        opt = 0;
        
      }}else{
        temp2.pb(i);
        mp[0]++;
        cnt = 0;
      }
    
  }
  if(!opt){
    cout << "NO" << endl;
    
  }else{
  cout << "YES" << endl;
  ll op = n;
  vector<ll> pos(n);
  for (ll x: temp2){
    //op--;
    pos[x] = op--;
  }
  for (ll x: temp1){
   // op--;
    pos[x] = op--;
  }
  for (ll x: pos){
    cout<<x << " ";
  }
  cout << endl;
  }
}

int main() 
{
  ll t; cin >> t;
  while (t--){
    bruh();
  }
}

Идея решения: Классическая задача на динамическое программирование.

Пусть у нас есть массив $$$a$$$. Для каждого значения $$$val = a[i]$$$ мы храним индексы его появления в массиве vec[val].

DP:

• Изначально: $$$dp[i+1] = dp[i]$$$, так как можно просто ничего не брать.
• Далее проверяем: если длина вхождений элемента $$$val$$$ уже хотя бы $$$val$$$, то можно образовать блок [val, val, ..., val] длиной ровно val.

Тогда обновляем:

где $$$j$$$ — индекс, откуда этот блок начинается.

Алгоритм:

1. Считаем массив, для каждого числа запоминаем позиции в vec.
2. Идём по массиву и обновляем dp:

• либо ничего не делаем;
• либо пытаемся собрать новый блок из одинаковых элементов.

1. В конце ответ равен $$$dp[n]$$$.

#include <iostream>
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define s second
#define f first
using namespace std;
void bruh(){
  ll n; cin >> n;
  vector<ll> a(n);
  for (ll i = 0;i<n;i++){
    cin >> a[i];
  }
  vector<vector<ll>> vec(n+1);
  vector<ll> dp(n+1,0);
  dp[0] = 0;
 // vec[a[0]].pb(0);
  for (ll i = 0;i<n;i++){
    vec[a[i]].pb(i);
    dp[i+1] = dp[i];
    ll val = a[i];
    if(vec[val].size()>=val){
      dp[i+1] = max(dp[i+1],dp[vec[val][vec[val].size()-val]]+val);
    }
  }
  cout << dp[n] << endl;
}

int main() 
{
  ll t; cin >> t;
  while (t--){
    bruh();
  }
}