Submission #1064060

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class dat{
public:
  ll val,mx,idx[10];
  dat(){val=mx=0,memset(idx,0,sizeof(idx));}
};

vector<dat> T(1);
string str;
ll val;
ll dfs(int pos,int idx,ll sum){
  if(idx<0){
    T[pos].mx-=T[pos].val;
    T[pos].val=max(T[pos].val,val);
    T[pos].mx+=T[pos].val;
    return T[pos].mx+sum;
  }

  int num=str[idx]-'0';
  if(!T[pos].idx[num])T[pos].idx[num]=T.size(),T.push_back(dat());
  ll res=dfs(T[pos].idx[num],idx-1,sum+T[pos].val);
  
  return T[pos].mx=max(T[pos].mx,res);;
}

int main(){
  int n;
  cin>>n;
  while(n--){
    cin>>str>>val;
    cout<<dfs(0,str.size()-1,0)<<endl;

  }
  return 0;
}

Submission Info

Judge Result