Submission #1064182

---

Source Code Expand

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

struct po{
  ll m,mx;
  po* ko[10];
};

po pool[1000005];
int poolcnt;

po* make_node(){
  po* res=&pool[poolcnt++];
  res->m=res->mx=0;
  for(int i=0;i<10;i++)res->ko[i]=NULL;
  return res;
}

ll dfs(int a,int b,po* p){
  if(!a){p->m+=b;return p->mx+=b;}
  if(p->ko[a%10]==NULL)p->ko[a%10]=make_node();
  ll s=dfs(a/10,b,p->ko[a%10])+p->m;
  p->mx=max(s,p->mx);
  return s;
}

int main(){
  int n;
  cin>>n;
  int a,b;
  po *o=make_node();
  o->mx=-1;
  for(int i=0;i<n;i++){
    cin>>a>>b;
    dfs(a,b,o);
    cout<<o->mx<<endl;
  }
  return 0;
}

Submission Info

Judge Result