Codeforces Round #817 (Div. 4) 1722D. Line Solution

 Problem  Link : https://codeforces.com/contest/1722/problem/D

Solution in C++:

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include <bits/stdc++.h>

using namespace std;

#define ll long long int

int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    ll  t;

    cin>>t;

    while(t--)

    {

        ll n;

        cin>>n;

        string s;

        cin>>s;

        ll i,total=0,minchange=0;

        vector<ll>diffarry;

        for(i=0; i<n; i++)

        {

            ll L,R;

            L=i;

            R=n-i-1;

            if(s[i]=='L')

            {

                if(L<R)

                {

                    minchange++;

                    total+=R;

                    diffarry.push_back(R-L);

                }

                else

                    total+=L;

            }

            else if(s[i]=='R')

            {

                if(L>R)

                {

                    minchange++;

                    total+=L;

                    diffarry.push_back(L-R);

                }

                else

                    total+=R;

            }

        }

        vector<ll>ans(n+1);

        for(i=minchange; i<=n; i++)

        {

            ans[i]=total;

        }

        sort(diffarry.begin(),diffarry.end(),greater<ll>());

        for(i=minchange-1;i>=1;i--)

        {

            total-=diffarry.back();

            diffarry.pop_back();

            ans[i]=total;

        }

        for(i=1;i<=n;i++)

            cout<<ans[i]<<" ";

        cout<<endl;

    }

}