1042B - Vitamins - CodeForces Solution

#include<iostream>
#include<vector>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<unordered_set>
#include<cmath>
#include<numeric>
#include<iterator>
#include<set>
#include<unordered_map>
#include<map>
#include<queue>
#include<cstring>
#include<stdio.h>
#include<fstream>
#include<iomanip>
#include<functional>
#include<bitset>
#include<chrono>
#include<climits>
#include<assert.h>

using namespace std;
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))

inline long long ceil_div(long long a, long long b) {
    return a / b + ((a ^ b) > 0 && a % b);
}
inline long long mod(long long a, long long b)
{
    return (a % b + b) % b;
}
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#define prime 1000000007
void google(int t) {cout << "Case #" << t << ": ";}
vector<ll> sieve(ll n) {ll*arr = new ll[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}

#define fo(i, k, n) for (int i = k; k < n ? i < n : i > n; k < n ? i++ : i--)
ll h[3];
ll w[3];
bool isset(int n, int i)
{
    return (n & (1 << i));
}

bool isPowerOfTwo(ll n)
{
    if (n == 0)
        return false;

    return (ceil(log2(n)) == floor(log2(n)));
}

void dfs1(int node,vector<pair<int,int>>adj[],set<int>&mp1,vector<int>&vis,int val)
{

  vis[node]=1;
  mp1.insert(val);
   for(auto it:adj[node])
   {
     if(!vis[it.first])
     {
        dfs1(it.first,adj,mp1,vis,val^it.second);
     }
   }
}


ll dp[10001][2][2][2];
ll f(int ind,int a,int b,int c,vector<ll>&v,vector<string>&v1)
{
  
  if(ind==v.size())
  {
     if(a>=1 && b>=1 && c>=1)
        return 0;
    else
        return INT_MAX;
  }
  if(dp[ind][a][b][c]!=-1)
    return dp[ind][a][b][c];
  ll ntake=f(ind+1,a,b,c,v,v1);
   ll take=INT_MAX;
  if(a!=1 || b!=1 || c!=1)
  {
      int cnt0=0,cnt1=0,cnt3=0;
       for(auto it:v1[ind])
       {
          if(it=='A')
            cnt0++;
        if(it=='B')
            cnt1++;
        if(it=='C')
            cnt3++;
       } 

       if((a<1 && cnt0>=1)||(b<1 && cnt1>=1)||(c<1 && cnt3>=1))
       {
           ll x=f(ind+1,min(a+cnt0,1),min(b+cnt1,1),min(c+cnt3,1),v,v1);
           if(x<INT_MAX)
            take=v[ind]+x;
        else
           take=x;
       }
  }
    //cout << take << " " << ntake <<endl;
  return dp[ind][a][b][c]=min(take,ntake);

}


void solve() {

ll n;
cin >> n;
vector<ll>v(n);
vector<string>v1(n);
for(int i=0;i<n;i++)
{
    cin >> v[i];
    cin >> v1[i];
}

memset(dp,-1,sizeof(dp));
ll x=f(0,0,0,0,v,v1);
if(x>=INT_MAX)
 cout << -1 <<endl;
else
    cout << x <<endl;


}

signed  main()
{
   
    ll t;
   t=1;
     
    for (ll i = 1; i <= t; ++i)
    {
        //google(i);
        solve();
    }
    return 0;
}