optimal game stratgy

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long int li;

#define test()    int test_case;cin>>test_case;while(test_case--)
#define fr(i,n) for(int i=0;i<n;i++)
#define frr(i,a,n) for(int i=a;i<n;i++)
#define sll(a) scanf("%lld",&a)
#define sl(a) scanf("%ld",&a)
#define si(a) scanf("%i",&a)
#define sd(a)  scanf("%ld",&a)
#define sf(a) scanf("%f",&a)
#define rn(a) return a
#define pai pair<int,int>
#define pal pair<li,li>
#define pall pair<lli,lli>
#define ff first
#define ss second
#define mod  1000000007
#define mp make_pair
#define pb push_back
#define pll(a) printf("%lld\n",a);
#define pl(a) printf("%lld\n",a);
#define pi(a) printf("%d\n",a);
#define pd(a) printf("%lf\n",a);
#define pf(a) printf("%f\n",a);
lli  dp[3000][3000];
int solve(lli  arr[],int start,int end)
 {
   if(start>end)return 0;
  if(dp[start][end]!=-1)
 {

  return dp[start][end];
  }
  else if(start==end)
   {
 
    return dp[start][start];
   
  }
  else if(start+1==end)
   {

 
    return max(arr[start],arr[start+1]);
   
   }
 //  else if(dp[start][end]!=-1) return dp[start][end];
   else
   {
   
    lli val1=arr[start]+min(solve(arr,start+2,end),solve(arr,start+1,end-1));
     lli  val2=arr[end]+min(solve(arr,start,end-2),solve(arr,start+1,end-1));
   
     dp[start][end]=max(val1,val2);
   }
return dp[start][end];
 }
int main()
{

int n;
lli arr[10000];
int t=1;
while(1)
 {
    cin>>n;
   lli  tot_sum=0;
     if(n==0) return 0;
    
    
     else
     {
      for(int i=0;i<n;i++)
{
cin>>arr[i];
      tot_sum+=arr[i];
}
}
for(int i=0;i<n;i++)
 {
   for(int j=0;j<n;j++)
   dp[i][j]=-1;
 }
for(int i=0;i<n;i++) dp[i][i]=arr[i];

solve(arr,0,n-1);
 cout<<dp[0][n-1]<<endl;
 }
}

ncr using inverse modulo

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define ll long long int
#define mod 1000000007

ll powmod(ll a,ll b)
    {
    b=mod-2;
    ll result=1;
    while(b)
        {
        if(b&1)
            result=(result*a)%mod;
        b=b>>1;
        a=(a*a)%mod;
    }
    return result;
}
int main() {

    int t,n,m,i;
    ll fact[201];
    fact[0]=fact[1]=1;
    for(i=2;i<201;i++)
        fact[i]=(fact[i-1]*i)%mod;
    scanf("%i",&t);
    while(t--)
        {
        scanf("%i%i",&n,&m);
        ll ans=fact[n]*powmod((fact[m],mod);
        printf("%lli\n",ans%mod);
    }
    return 0;
}

all destination shortest path using dijkestra and priority queue

#include <iostream>
using namespace std;
#include<bits/stdc++.h>
typedef long long int lli;
int visited[10010];
lli dist[10010];
#define pp pair<int,int>
// comparator for min heap
class Prioritize
{
public:
    int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 )
    {
        return p1.second > p2.second;
    }
};

int main()
{
    int t;
     cin>>t;
      while(t--)
       {
        list<pair<lli,lli> >li[10010];
        lli n,m;
 
       cin>>n>>m;
       
          for(int i=0;i<m;i++)
           {
            lli a,b,c;
             cin>>a>>b>>c;
            li[a].push_back(make_pair(b,c));
            li[b].push_back(make_pair(a,c));
           
           }
         
             

            for(int i=1;i<=n;i++)
             {
              visited[i]=0;
              dist[i]=INT_MAX;
}


//  declaring pq;
            priority_queue<pp, vector<pp > , Prioritize > q;
           dist[1]=0;
       
           lli ans=0;
           int f=0;
           // need to find distance of all node from 1
           lli start=1;
           q.push(make_pair(1,0));
           while(!q.empty())
            {
           
   
            list<pair<lli,lli> > :: iterator it;
            lli start=q.top().first;
         
           
             q.pop();
            if(visited[start]==1) continue;
            visited[start]=1;
         
            for(it=li[start].begin();it!=li[start].end();it++)
             {
       
              if(!visited[it->first]  && dist[it->first]>dist[start]+it->second)
              {
             
               q.push(make_pair(it->first,dist[start]+it->second));
             
                dist[it->first]=dist[start]+it->second;
              }
             
             }
             
}
               

           
           for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
         }
         return 0;
       }
     
     

INVERSION_COUNT

#include<iostream>
using namespace std;
 typedef long long int lli;
    lli temp[10000000];
      lli arr[1000000+10];
 #include<bits/stdc++.h>
 lli ic=0;
lli merge (lli arr[],lli start,lli mid,lli end)
   {
 
     lli i=start, j=mid+1;
     lli p=start;
   
      lli lc=0;
       while(i<=mid && j<=end)
        {
       
        if(arr[i]>arr[j])
        {
        lc+=mid-i+1;
        temp[p++]=arr[j];
        j++;
}
else
{
temp[p++]=arr[i++];
}
       
}
while(i<=mid) temp[p++]=arr[i++];
while(j<=end) temp[p++]=arr[j++];
for(int i=start;i<p;i++) arr[i]=temp[i];
return lc;
   }
 
 void  divide(lli arr[],lli start,lli end)
  {
 
  if(start<end)
  {
 
  lli mid=(start+end)/2;
 
  divide(arr,start,mid);
  divide(arr,mid+1,end);
  ic+=merge(arr,start,mid,end);
  }
 

  }
 
 int  main()
  {
  int t;
  cin>>t;
  while(t--)
   {
    ic=0;
    lli n;
    cin>>n;
 
    for(int i=0;i<n;i++)
     {
       cin>>arr[i];
       
 }
 divide(arr,0,n-1);
  cout<<ic<<endl;
}
return 0;
  }