Submission #1064079

---

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].val+=val;
    return T[pos].mx+T[pos].val+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);
  T[pos].mx=max(T[pos].mx,res-sum-T[pos].val);
  return res;
}

int main(){
  int n;
  cin>>n;
  while(n--){
    cin>>str>>val;
    dfs(0,str.size()-1,0);
    cout <<T[0].mx<<endl;
  }
  return 0;
}

Submission Info

Judge Result