1381B - Unmerge - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define f(i, a, b) for (ll i = a; i < b; i++)
#define fr(i, a, b) for (ll i = b - 1; i >= a; i--)
#define fa(x) for (auto ele : x)

#define all(x) (x).begin(), (x).end()
#define ll long long
#define db double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ppiii pair<pair<int, int>, int>

#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vs vector<string>
#define v(ele) vector<ele>

#define sei set<int>
#define sel set<ll>
#define ses set<string>
#define sec set<char>
#define se(ele) set<ele>

#define mii map<int, int>
#define mll map<ll, ll>
#define mipii map<int, pair<int, int>>
#define mcpii map<char, pair<int, int>>
#define mcpci map<char, pair<char, int>>
#define mpiii map<pair<char, int>, int>
#define mic map<int, char>
#define mci map<char, int>
#define mcsei map<char, sei>
#define mlsel map<ll, sel>
#define mcvi map<char, vi>
#define mci map<char, int>
#define msi map<string, int>
#define misei map<int, sei>
#define mlvl map<ll, vl>
#define mivi map<int, vi>
#define mlpll map<ll, pll>
#define mplll map<pll, ll>
#define m(e1, e2) map<e1, e2>

#define qi queue<int>
#define ql queue<ll>
#define qpii queue<pair<int, int>>

const ll mod = 1e9 + 7;
const ll INF = 1e16;
const ll NEG_INF = LONG_LONG_MIN;

const ll N = 1e3 + 5;
// const int N = 51;

void YN(bool possible)
{
    if (possible)
    {
        cout << "YES\n";
    }
    else
    {
        cout << "NO\n";
    }
}
void solve()
{
    int n;
    cin >> n;
    int arr[2 * n];
    f(i, 0, 2 * n)
    {
        cin >> arr[i];
    }
    vi v;
    int cnt = 1, rep = arr[0];
    f(i, 1, 2 * n)
    {
        if (rep < arr[i])
        {
            v.push_back(cnt);
            rep = arr[i];
            cnt = 1;
        }
        else
        {
            cnt++;
        }
    }
    v.push_back(cnt);
    int len = v.size();
    bool dp[n + 1]{0};
    dp[0] = 1;
    f(i, 0, len)
    {
        int val = v[i];
        // dp[val] = 1;
        fr(j, 0, n - val + 1)
        {
            if (dp[j])
            {
                dp[j + val] = 1;
            }
        }
    }
    YN(dp[n]);
    return;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}