Submission #372405

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RREP(i,n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int> > pipii;
typedef vector<int> vi;

const int INF = 1e9;
const int MOD = 1e9+7;

typedef ll Data;
struct Trie{
    Data data;
    Data m;
    bool tail;
    Trie *prev;
    Trie *next[10];
    Trie(){data=0LL;m=0LL;tail=false;prev=(Trie*)0;fill(next, next+10, (Trie*)0);}
};
void insert(char *t, Trie *r, Data data=0){
    //cout << "char :" << *t << endl;
    if(!(*t)){
        r->data = r->data + data;
        r->m = r->m + data;
        Data m = 0LL;
        m = r->m;
        while(r->data != -1LL){
            r = r->prev;
            m = max(r->m, m + r->data);
            r->m = m;
        }
        return;
    }
    int c = (*t) - '0';
    if(!r->next[c]){
        r->next[c] = new Trie();
        r->next[c]->prev = r;
    }
    insert(t+1, r->next[c], data);
}

int main(void){
    int n;
    cin >> n;
    Trie *top = new Trie();
    top->data = -1;
    REP(i, n){
        string ss; int k;
        cin >> ss >> k;
        char s[15];
        REP(j, ss.size()){
            s[j] = ss[ss.size()-j-1];
            s[j+1] = '\0';
        }
        insert(s, top, k);
        cout << top->m + 1 << endl; 
    }

    return 0;
}

Submission Info

Judge Result